Overview

This problem asks us to find the total number of pairs of club members \((i, j)\) chosen from \(N\) members such that the sum of their technical skills is at least \(X\) and the sum of their physical strengths is at least \(Y\).

Analysis

Naive Approach and Its Limitations

A first thought might be to brute-force all pairs of members \((i, j)\) (\(1 \le i < j \le N\)) and check whether they satisfy the conditions \(A_i + A_j \ge X\) and \(B_i + B_j \ge Y\). However, the total number of pairs to choose is \(\frac{N(N - 1)}{2} \approx \frac{10^{10}}{2} = 5 \times 10^9\), resulting in a time complexity of \(O(N^2)\), which exceeds the time limit and results in TLE (Time Limit Exceeded).

Reformulation for Efficient Counting

Rearranging the conditions with respect to member \(i\) and member \(j\), we get: - \(A_j \ge X - A_i\) - \(B_j \ge Y - B_i\)

This can be viewed as a 2D range query (counting points in a multidimensional subspace) problem: “How many members \(j\) satisfy the conditions for member \(i\)?” To quickly count pairs that satisfy both conditions simultaneously, a standard technique is to order one condition (the condition on \(A\)) by sorting and manage the other condition (the condition on \(B\)) using a data structure (such as a BIT).

Furthermore, to maintain the index order relationship (\(i < j\)), using divide and conquer (CDQ divide and conquer) is very effective.

Algorithm

This solution combines divide and conquer, a Binary Indexed Tree (BIT), and coordinate compression.

1. Coordinate Compression

Since \(B_i\) and \(Y - B_i\) can be as large as \(2 \times 10^9\), they cannot be directly used as array indices. We collect all occurring values of \(B_i\) and \(Y - B_i\) (at most \(2N\) values), remove duplicates, sort them, and determine the rank of each value (its compressed index).

2. Divide and Conquer (CDQ Divide and Conquer)

Consider a function solve(l, r) that counts the pairs within the interval \([l, r)\). Let the midpoint be \(m = \lfloor (l + r) / 2 \rfloor\). The pairs \((i, j)\) can be categorized into three cases: 1. \(l \le i < j < m\) (both are in the left half) \(\to\) recursive call solve(l, m) 2. \(m \le i < j < r\) (both are in the right half) \(\to\) recursive call solve(m, r) 3. \(l \le i < m \le j < r\) (\(i\) is in the left half, \(j\) is in the right half)

We efficiently count the number of pairs spanning across halves in “3. \(i\) in the left and \(j\) in the right”.

3. Plane Sweep and Counting with a BIT

For \(l \le i < m \le j < r\), the conditions to satisfy are \(A_j \ge X - A_i\) and \(B_j \ge Y - B_i\). We treat these as “events” and categorize them as follows: - Point addition event (right side \(j\)): value \(A_j\), coordinate \(B_j\) - Query event (left side \(i\)): value \(X - A_i\), condition \(\ge Y - B_i\)

We sort these events in descending order of the first key (value) and sweep through them. 1. By processing in descending order of values, when processing a query \(X - A_i\), exactly the elements \(j\) from the right side satisfying \(A_j \ge X - A_i\) will have already been added to the BIT. 2. In the BIT, we add \(+1\) at the coordinate position corresponding to \(B_j\). 3. When a query \(i\) arrives, we query the BIT for the “count of elements \(\ge Y - B_i\)” and add it to the answer. 4. After all events are processed, we restore the BIT to its original state (all zeros) for subsequent calculations.

Complexity

• Time Complexity: \(O(N \log^2 N)\)
  • Coordinate compression takes \(O(N \log N)\).
  • The recursion depth of the divide-and-conquer is \(O(\log N)\).
  • At each depth, for each interval of length \(K\), sorting the events takes \(O(K \log K)\) and the BIT operations take \(O(K \log N)\). Since the sum of interval lengths across any single level is \(N\), each level takes \(O(N \log N)\), yielding \(O(N \log^2 N)\) in total. This easily passes within the time limit even for \(N = 10^5\).
• Space Complexity: \(O(N)\)
  • It operates with \(O(N)\) memory, including the arrays for coordinate compression, the BIT, and the recursion call stack.

Implementation Notes

• Tie-breaking in Descending Sort: In boundary cases where \(A_j = X - A_i\), point additions must be performed before queries. By defining addition events as type = 1 and query events as type = 0 and sorting the tuple (value, type, ...) in descending order, type = 1 (addition) naturally comes first when values are equal.

• BIT Reset/Initialization Method: If the BIT is completely reinitialized at each step of the divide-and-conquer using something like bit = [0] * M, the reinitialization alone would take \(O(N^2)\) time. By recording the modified indices in a list and subtracting the added values to reset them to \(0\), the BIT can be reused without increasing the time complexity.

• Python Recursion Limit: Since the recursion depth of the divide-and-conquer algorithm can become large, it is necessary to increase the recursion limit using sys.setrecursionlimit.

  Source Code

import sys
import bisect

# 再帰深度の上限を増やす
sys.setrecursionlimit(300000)

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    X = int(data[1])
    Y = int(data[2])
    
    A = [0] * N
    B = [0] * N
    ptr = 3
    for i in range(N):
        A[i] = int(data[ptr])
        B[i] = int(data[ptr+1])
        ptr += 2
        
    vals = sorted(list(set(B + [Y - b for b in B])))
    M = len(vals)
    
    B_comp = [bisect.bisect_left(vals, b) for b in B]
    Y_B_comp = [bisect.bisect_left(vals, Y - b) for b in B]
    
    bit = [0] * (M + 2)
    
    def solve(l, r):
        if r - l <= 1:
            return 0
        m = (l + r) // 2
        ans = solve(l, m) + solve(m, r)
        
        # R の点イベント (type=1) と L のクエリイベント (type=0)
        events = [(A[j], 1, B_comp[j]) for j in range(m, r)] + [(X - A[i], 0, Y_B_comp[i]) for i in range(l, m)]
        events.sort(reverse=True)
        
        total_added = 0
        added = []
        step_ans = 0
        
        for val, type_, b_val in events:
            if type_ == 1:
                total_added += 1
                idx = b_val + 1
                added.append(idx)
                while idx <= M:
                    bit[idx] += 1
                    idx += idx & (-idx)
            else:
                if b_val == 0:
                    step_ans += total_added
                else:
                    s = 0
                    idx = b_val
                    while idx > 0:
                        s += bit[idx]
                        idx -= idx & (-idx)
                    step_ans += total_added - s
                    
        for idx in added:
            while idx <= M:
                bit[idx] -= 1
                idx += idx & (-idx)
                
        return ans + step_ans

    ans = solve(0, N)
    print(ans)

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.8-flash-high.