CF Round #725 C - Number of Pairs


Tags:cpcodeforcesdiv3binary_searchmath

問題

https://codeforces.com/contest/1538/problem/C

問題文

nn 要素の数列 aa と、 l,rl, r が与えられる。 1i<jn1 \le i < j \le n かつ lai+ajrl \le a_i + a_j \le r を満たす (i,j)(i, j) の組の個数は?

制約

  • 1t1041 \le t \le 10^4
  • 1n2×1051 \le n \le 2 \times 10^5
  • 1lr1091 \le l \le r \le 10^9
  • 1ai1091 \le a_i \le 10^9
  • nn の総和は 2×1052 \times 10^5 を超えない

サンプル

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

考察

まあ全列挙して数えてると O(n2)O(n^2) で間に合わないので、どうせ二分探索。

ii に対して、 jj が何通りあるかを調べればいい。

コード

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