問題
https://codeforces.com/contest/1538/problem/C (新しいタブで開く)
問題文
要素の数列 と、 が与えられる。 かつ を満たす の組の個数は?
制約
- の総和は を超えない
サンプル
4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1
2
7
0
1
考察
まあ全列挙して数えてると で間に合わないので、どうせ二分探索。
各 に対して、 が何通りあるかを調べればいい。
コード
https://codeforces.com/contest/1538/submission/125442982 (新しいタブで開く)
当時 lower_bound
とか upper_bound
とか知らなかった人です。
void solve() {
ll n, l, r;
cin >> n >> l >> r;
vector<ll> a(n);
rep(i, n) { cin >> a[i]; }
sort(a.begin(), a.end());
ll ans = 0;
rep(i, n - 1) {
ll l_ok = i, l_ng = n;
while (abs(l_ok - l_ng) > 1) {
ll mid = (l_ok + l_ng) / 2;
if (a[i] + a[mid] < l) {
l_ok = mid;
}
else {
l_ng = mid;
}
}
ll r_ok = i, r_ng = n;
while (abs(r_ok - r_ng) > 1) {
ll mid = (r_ok + r_ng) / 2;
if (a[i] + a[mid] <= r) {
r_ok = mid;
}
else {
r_ng = mid;
}
}
ans += max(0LL, r_ok - l_ok);
}
cout << ans << endl;
}