fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. // count number of pairs (i<j) in sorted array A whose sum ≤ X
  6. ll count_le(const vector<ll>& A, ll X) {
  7.     int n = A.size();
  8.     ll cnt = 0;
  9.     int i = 0, j = n - 1;
  10.     while (i < j) {
  11.         if (A[i] + A[j] <= X) {
  12.             // for this i, all indices from i+1..j paired with i are ≤ X
  13.             cnt += (j - i);
  14.             ++i;
  15.         } else {
  16.             // sum too large, decrease j
  17.             --j;
  18.         }
  19.     }
  20.     return cnt;
  21. }
  22.  
  23. int main(){
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(nullptr);
  26.  
  27.     int T;
  28.     cin >> T;
  29.     while (T--) {
  30.         int n;
  31.         ll l, r;
  32.         cin >> n >> l >> r;
  33.         vector<ll> a(n);
  34.         for (int i = 0; i < n; i++) {
  35.             cin >> a[i];
  36.         }
  37.  
  38.         sort(a.begin(), a.end());
  39.         // #pairs with sum ≤ r minus #pairs with sum ≤ l-1
  40.         ll ans = count_le(a, r) - count_le(a, l - 1);
  41.         cout << ans << "\n";
  42.     }
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
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
stdout
copy 
2
7
0
1
https://ideone.com/gsQ0EZ
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!