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\). Since \(N \le 10^5\), enumerating all pairs in \(O(N^2)\) will result in TLE, so we reduce the time complexity to \(O(N\log N)\) using sorting + binary search + BIT (Fenwick tree).

Analysis

Naive Approach

If we check all pairs \((i,j)\) using a double loop, the number of pairs is approximately \(\frac{N^2}{2} = 5\times 10^9\), which will definitely result in TLE.

Transforming the Condition by Fixing One Element

Fixing member \(i\), the conditions become:

• \(A_j \ge X - A_i\)
• \(B_j \ge Y - B_i\)

This forms “two lower bound conditions on \(j\)”. In other words, this problem reduces to counting the number of points \((A_j,B_j)\) on a 2D plane that fall into the upper-right quadrant (2D dominance counting).

If there were only one condition (for example, only on \(A\)), we could simply sort \(A\) and use binary search. However, with two conditions, simple sorting alone cannot determine “the number of elements that also satisfy the condition on \(B\) among the set satisfying the condition on \(A\),” so we need a cleverer approach.

Solution Strategy: Process One in Sorted Order, Manage the Other with a BIT

First, sort the points in ascending order of \(A\). Then, as we iterate through \(i\) in increasing order of \(A\), the

\[\text{threshold } thr = X - A_i\]

decreases monotonically. Therefore, “the set of \(j\) satisfying \(A_j \ge thr\)” forms a contiguous suffix from the end of the sorted array, and this interval only expands (never shrinks) as \(i\) increases.

Therefore, by using a two-pointer approach to progressively add “points satisfying the condition on \(A\)” into a BIT, and querying the BIT to count how many among the inserted points satisfy \(B_j \ge Y - B_i\), we can compute the answer for each \(i\) in \(O(\log N)\).

Handling Duplicates and Self-Pairs

With this counting method, both \((i,j)\) and \((j,i)\) are counted (as ordered pairs). Furthermore, self-pairs where \(j=i\) are also counted if they satisfy the conditions (\(2A_i \ge X\) and \(2B_i \ge Y\)). Therefore, we can compute:

\[\text{Answer} = \frac{(\text{Total counted}) - (\text{Number of elements satisfying the condition with themselves})}{2}\]

Since the conditions are symmetric with respect to \(i\) and \(j\), this formula holds.

Algorithm

1. Sort the points \((A_i,B_i)\) in ascending order of \(A\) to obtain arrays A and B.
2. Coordinate compress the values of B (since values can be up to \(10^9\), they cannot be used directly as BIT indices). Let us be the sorted array of unique values in B, and rank[i] be the rank of B[i] (1-indexed).
3. Initialize a BIT (of size \(m=|us|\), tracking the count at each position) and set pointer p = n (elements from index p onwards are already inserted).
4. For \(i = 0,1,\dots,N-1\) in order:
   • Set thr = X - A[i]. While A[p-1] >= thr, decrement p and add \(+1\) to the BIT at that point’s rank.
   • Set t = Y - B[i], find idx = bisect_left(us, t) (which is the number of values where \(B < t\)), and query the BIT to find s, the “number of inserted points where \(B < t\)”.
   • Since the total number of inserted points is n - p, the number of points satisfying the condition is (n - p) - s. Add this to total.
5. Count the number of indices \(i\) where \(2A_i \ge X\) and \(2B_i \ge Y\), denoted as self_.
6. Output (total - self_) // 2.

Example

When \(N=3, X=5, Y=5\), and the points are \((1,4),(3,3),(4,2)\) (already in ascending order of \(A\)):

• \(i=0\): \(thr=4\) \(\to\) insert \((4,2)\). \(t=5-4=1\) \(\to\) there is 1 point with \(B\ge1\). total=1
• \(i=1\): \(thr=2\) \(\to\) insert \((3,3)\) (inserted: \(\{2,3\}\)). \(t=2\) \(\to\) 2 points. total=3
• \(i=2\): \(thr=1\) \(\to\) insert \((1,4)\) (inserted: \(\{2,3,4\}\)). \(t=3\) \(\to\) 2 points with \(B\ge3\). total=5
• Self-pairs: only \((3,3)\) (\(6\ge5, 6\ge5\)) \(\to\) self_=1
• Answer: \((5-1)/2 = 2\)

Indeed, the pairs satisfying the conditions are \(\{(1,4),(4,2)\}\) (sums \(5,6\)) and \(\{(3,3),(4,2)\}\) (sums \(7,5\)), which gives 2 pairs, matching our result.

Complexity

• Time Complexity: \(O(N \log N)\) (sorting, binary search for coordinate compression, and each BIT operation take \(O(\log N)\); p moves at most \(N\) times in total)
• Space Complexity: \(O(N)\)

Implementation Notes

• Do not rewind pointer p: Sorting A in ascending order makes the threshold monotonically decrease, so p only ever decreases. Thus, points are inserted at most \(N\) times in total. Note that sorting in reverse order would break this monotonicity.

• Coordinate compression: Since \(B_i \le 10^9\), it cannot be used directly as a BIT index. Compress it using sorted(set(B)) and find ranks using bisect_left.

• Counting “\(B \ge t\)”: Since a BIT excels at prefix sums, we first find idx = bisect_left(us, t) (the number of compressed positions with \(B<t\)), compute the sum s on the BIT interval \([1,\,idx]\) (the “number of inserted points with \(B<t\)”), and take (total inserted) - s. If \(t \le 0\), idx = 0, correctly yielding all inserted elements.

• Converting from ordered to unordered pairs: Do not forget to subtract self-pairs and divide by 2 at the end. Since \(X\) and \(Y\) can be up to \(2\times10^9\), and \(2A_i\) can be similarly large, 64-bit integers should be used in languages like C++ (the answer itself can also reach about \(5\times10^9\)).

• Fast I/O: Since there are \(N=10^5\) lines of input, reading everything at once with sys.stdin.buffer.read().split() in Python is recommended. For the BIT as well, inlining loops instead of function calls can be faster.

  Source Code

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); X = int(data[1]); Y = int(data[2])
    pts = sorted((int(data[3 + 2 * i]), int(data[4 + 2 * i])) for i in range(n))
    A = [p[0] for p in pts]
    B = [p[1] for p in pts]

    us = sorted(set(B))
    m = len(us)
    rank = [bisect_left(us, b) + 1 for b in B]

    tree = [0] * (m + 1)
    p = n
    total = 0
    for i in range(n):
        thr = X - A[i]
        while p > 0 and A[p - 1] >= thr:
            p -= 1
            k = rank[p]
            while k <= m:
                tree[k] += 1
                k += k & -k
        t = Y - B[i]
        idx = bisect_left(us, t)
        s = 0
        k = idx
        while k > 0:
            s += tree[k]
            k -= k & -k
        total += (n - p) - s

    self_ = 0
    for i in range(n):
        if 2 * A[i] >= X and 2 * B[i] >= Y:
            self_ += 1

    sys.stdout.write(str((total - self_) // 2) + "\n")

main()

---

This editorial was generated by claude5opus-high.