Overview

This problem asks us to count the number of pairs \((i,j)\) chosen from \(N\) people such that \(A_i+A_j \ge X\) and \(B_i+B_j \ge Y\). This is a typical problem of “counting pairs that satisfy two conditions simultaneously,” which can be solved by sorting and a two-pointer approach for one condition, and a BIT (Fenwick tree) for the other.

Analysis

Naive Approach

Checking all pairs \((i,j)\) exhaustively takes \(O(N^2)\) time. For \(N = 10^5\), this requires roughly \(5 \times 10^9\) checks, which will result in TLE.

Observation 1: Counting Ordered Pairs is Easier to Handle

The constraint “\(i < j\)” can be cumbersome because it requires looking at only one side. Instead, we can first count the number of ordered pairs \((i,j)\) with \(i \ne j\) that satisfy the conditions. Since the conditions \(A_i+A_j\ge X\) and \(B_i+B_j\ge Y\) are symmetric with respect to \(i,j\), if \((i,j)\) satisfies the conditions, \((j,i)\) also satisfies them. Therefore:

\[(\text{Answer}) = \frac{(\text{Number of ordered pairs})}{2}\]

In terms of implementation, it is easier to first count assuming that \(j\) can be \(i\) itself, and then subtract the cases where \(i=j\) (i.e., indices \(i\) such that \(2A_i \ge X\) and \(2B_i \ge Y\)).

Observation 2: Sorting by \(A\) Makes Condition 1 a “Suffix”

Sort the pairs in ascending order of \(A\) (hereinafter, let the sorted arrays be \(a, b\)). For a fixed \(i\), the set of indices \(j\) satisfying \(a_i + a_j \ge X\), or equivalently \(a_j \ge X - a_i\), forms a contiguous range at the end of the array (a suffix) \([p_i, N)\) because the array is sorted.

Furthermore, as we move \(i\) from smaller to larger values, \(a_i\) monotonically increases, so the threshold \(X - a_i\) monotonically decreases, and the boundary \(p_i\) moves monotonically to the left. Thus, we can maintain \(p\) across the entire algorithm in \(O(N)\) time using a two-pointer approach.

Observation 3: Condition 2 is the Count of “\(b_j \ge\) threshold” within the Range

What remains is to find the “count of indices \(j\) in the suffix \([p,N)\) satisfying \(b_j \ge Y - b_i\).” As \(i\) advances, elements are only added to the suffix (never removed). Therefore, if we insert \(b_j\) into a BIT whenever an element is added, we only need to query “the number of inserted elements whose value is greater than or equal to \(Y-b_i\).”

Since the values of \(b\) can be up to \(10^9\), we use coordinate compression to keep the size of the BIT down to \(O(N)\).

Algorithm

1. Sort \((A_i, B_i)\) in ascending order of \(A\), and let the resulting arrays be \(a, b\).
2. Coordinate compress the values of \(b\), and prepare a BIT of size \(M \le N\) (to maintain the frequency of each value).
3. Initialize the pointer \(p = N\), and counters \(total = 0\), \(selfCount = 0\).
4. For \(i = 0, 1, \dots, N-1\) in order:
   • While \(a_{p-1} \ge X - a_i\), decrement \(p\) by \(1\) and insert that \(b_p\) into the BIT (also updating the count of inserted elements, \(inBit\)). Now the BIT contains all \(b\) values of \(j\) satisfying Condition 1.
   • Let \(need = Y - b_i\). Find the first position \(pos\) in the compressed coordinates that is greater than or equal to \(need\) via binary search, and compute: $\(cnt = inBit - (\text{sum of BIT over } [0,pos))\)\( which gives the "count of elements with \)b_j \ge need\(", and add it to \)total$.
   • If \(i\) itself is included in the suffix (\(i \ge p\)) and \(2b_i \ge Y\), then \(j=i\) was mistakenly counted, so increment \(selfCount\) by \(1\).
5. The answer is \((total - selfCount)/2\).

Concrete example: When \(N=3\), \(X=5\), \(Y=5\), \((A,B) = (1,4),(3,3),(4,1)\). This is already sorted in ascending order of \(A\). - \(i=0\) (\(a=1\)): \(a_j \ge 4\) is required \(\to\) only \(j=2\) is inserted into the BIT. Count of \(b_j \ge 1\) \(= 1\). - \(i=1\) (\(a=3\)): \(a_j \ge 2\) \(\to\) \(j=1,2\) are inserted. Count of \(b_j \ge 2\) \(=1\) (\(b_1=3\)). For \(i=1\) itself, \(2b_1=6\ge5\), so it corresponds to a self-pair \(\to\) \(selfCount=1\). - \(i=2\) (\(a=4\)): \(a_j\ge1\) \(\to\) all elements are inserted. Count of \(b_j\ge4\) \(=1\) (\(b_0=4\)). From \(total = 3\) and \(selfCount = 1\), the answer is \((3-1)/2 = 1\) (indeed, the \(1\)st and \(2\)nd pairs, \((1,4)\) and \((3,3)\), satisfy the conditions).

Complexity

• Time Complexity: \(O(N \log N)\) (sorting, binary searching during coordinate compression, and each BIT operation take \(O(\log N)\); pointer movements take \(O(N)\) in total)
• Space Complexity: \(O(N)\)

Implementation Notes

• Beware of overflow: \(X, Y \le 2\times10^9\) can exceed the range of 32-bit signed integers during addition, so read them using long long (not a concern in Python, but mandatory in C++). Calculations like \(X - a_i\) and \(Y - b_i\) should also use 64-bit integers. The answer can also reach around \(5\times 10^9\), so long long is required.

• Querying “the count of elements greater than or equal to a threshold” with a BIT: Since a BIT is suited for prefix sums, calculate this as (total inserted) - (count of elements strictly less than the threshold). We utilize the fact that the index \(pos\) obtained via lower_bound corresponds to the “number of elements strictly less than \(need\).”

• Do not forget to exclude \(j = i\): Index \(i\) itself may be included in the suffix satisfying Condition 1 (when \(2a_i \ge X\)). If \(2b_i \ge Y\) also holds, this case must be subtracted; otherwise, the answer will be off.

• Handling duplicate values: Even if there are duplicate values in \(A\), writing the two-pointer condition with a weak inequality as a[p-1] >= X - a[i] correctly captures the suffix (since we count ordered pairs and divide by \(2\) at the end, sorting stability and tie-breaking do not affect the result).

• While this can also be implemented using square root decomposition or merge sort (counting similarly to inversions without a BIT), using a BIT is the most concise approach.

  Source Code

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<int> t;
    BIT(int n_=0):n(n_),t(n_+1,0){}
    void add(int i,int v){ for(++i;i<=n;i+=i&-i) t[i]+=v; }
    int sum(int i){ int s=0; for(;i>0;i-=i&-i) s+=t[i]; return s; } // prefix [0,i)
};

int main(){
    int N; long long X, Y;
    scanf("%d %lld %lld", &N, &X, &Y);
    vector<long long> A(N), B(N);
    for(int i=0;i<N;i++){
        long long a,b; scanf("%lld %lld",&a,&b);
        A[i]=a; B[i]=b;
    }
    vector<int> idx(N);
    for(int i=0;i<N;i++) idx[i]=i;
    sort(idx.begin(), idx.end(), [&](int x,int y){ return A[x]<A[y]; });
    vector<long long> a(N), b(N);
    for(int i=0;i<N;i++){ a[i]=A[idx[i]]; b[i]=B[idx[i]]; }

    vector<long long> comp = b;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int M = comp.size();
    BIT bit(M);

    auto compIdx=[&](long long v)->int{
        return (int)(lower_bound(comp.begin(), comp.end(), v) - comp.begin());
    };

    long long total = 0;
    long long selfCount = 0;
    int p = N;
    int inBit = 0;
    for(int i=0;i<N;i++){
        while(p>0 && a[p-1] >= X - a[i]){
            p--;
            bit.add(compIdx(b[p]), 1);
            inBit++;
        }
        // count j in [p,N) with b[j] >= Y - b[i]
        long long need = Y - b[i];
        int pos = compIdx(need); // first index with comp >= need
        long long cnt = (long long)inBit - bit.sum(pos);
        total += cnt;
        if(i >= p && 2*b[i] >= Y) selfCount++;
    }
    long long ans = (total - selfCount)/2;
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude5opus-high.