C - Number of Pairs

問題

https://codeforces.com/contest/1538/problem/C (新しいタブで開く)

問題文

$n$ 要素の数列 $a$ と、 $l, r$ が与えられる。 $1 \le i < j \le n$ かつ $l \le a_i + a_j \le r$ を満たす $(i, j)$ の組の個数は？

制約

• $1 \le t \le 10^4$
• $1 \le n \le 2 \times 10^5$
• $1 \le l \le r \le 10^9$
• $1 \le a_i \le 10^9$
• $n$ の総和は $2 \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(n^2)$ で間に合わないので、どうせ二分探索。

各 $i$ に対して、 $j$ が何通りあるかを調べればいい。

コード

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