問題
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; }