Summary

We count the number of pairs of club members whose sum of technical skills is at least \(X\) and sum of physical strengths is at least \(Y\). By sorting by technical skill, adding candidates sequentially, and using a Fenwick Tree (BIT), we can quickly find the number of people who satisfy the physical strength condition.

Analysis

Checking All Pairs Is Too Slow

Checking all pairs \((i,j)\) takes \(O(N^2)\) time. When \(N=10^5\), approximately \(50\) billion pairs would need to be checked, which cannot pass within the time limit.

Therefore, we consider fixing \(1\) member and counting the number of valid partners for that member all at once.

For a member with technical skill \(a\) and physical strength \(b\), the requirements for a partner are as follows:

• Technical skill is at least \(X-a\)
• Physical strength is at least \(Y-b\)

Candidates Satisfying the Technical Skill Condition Can Be Managed by Insertions Only

We sort the members in ascending order of technical skill and process each member in that order.

As the technical skill \(a\) of the member of interest increases, the lower bound \(X-a\) for the partner’s technical skill decreases. In other words, candidates satisfying the technical skill condition only increase, and once a candidate is added, they never need to be removed.

Thus, we can move a pointer from the end of the sorted array and sequentially add members whose technical skill is at least \(X-a\) into our data structure.

Since each member is added at most \(1\) time, the total number of candidate additions is \(O(N)\).

Counting the Physical Strength Condition with a Fenwick Tree

Among the candidates, the number of people with physical strength at least \(Y-b\) can be obtained by:

\(\text{total number of candidates} - \text{number of candidates with physical strength less than } Y-b\)

A Fenwick Tree is a data structure that maintains the counts for each value and can compute the “sum of counts from the beginning up to a certain position” in \(O(\log N)\). Using this, we can quickly count the number of candidates whose physical strength is strictly less than a given threshold.

However, since physical strength can be up to \(10^9\), we cannot use its value directly as an array index. We perform coordinate compression, which sorts the physical strength values in ascending order and replaces each with a contiguous index.

Beware of Self-Pairing and Double Counting

With this method, the candidates may include the member themselves.

The condition under which the member themselves is counted is:

\(2a \ge X\) and \(2b \ge Y\)

When this happens, we subtract \(1\) from the counted number.

Furthermore, each valid pair of \(2\) distinct members is counted twice depending on which member is considered first. Therefore, dividing the final total by \(2\) gives the answer.

Algorithm

1. Sort the members in ascending order of technical skill.

2. Create an array values containing unique physical strength values sorted in ascending order.

   • Assign \(1\)-based indices to each element in values.
   • In the Fenwick Tree, record the number of candidates with the physical strength corresponding to each index.

3. Initialize the following variables:

   • p: The index of the member with the maximum technical skill among those not yet added
   • inserted: The total number of candidates added so far
   • answer: The cumulative count of partners satisfying the conditions

4. For each member \((a,b)\) in sorted order, perform the following:

① Add members who satisfy the technical skill condition

While the technical skill of members[p] is at least \(X-a\), add \(1\) to the position in the Fenwick Tree corresponding to that member’s physical strength. After that, increment inserted and move p to the left.

After this process, the Fenwick Tree contains exactly those members whose technical skill is at least \(X-a\).

② Find the number of members who satisfy the physical strength condition

Use bisect_left(values, Y-b) to find the number of distinct values k whose physical strength is strictly less than \(Y-b\).

Let below be the prefix sum of the first k elements in the Fenwick Tree; the number of members satisfying both conditions is inserted - below. Add this to answer.

For example, if the candidates’ physical strengths are \([2,5,5,9]\) and the partner requires physical strength at least \(5\), there is \(1\) person with physical strength strictly less than \(5\), so the number of members satisfying the condition is \(4-1=3\).

③ Exclude the member themselves

If \(2a \ge X\) and \(2b \ge Y\), the member themselves has also been counted, so subtract \(1\) from answer.

1. Since each pair has been counted \(2\) times, output answer // 2.

Complexity

• Time complexity: \(O(N\log N)\)
• Space complexity: \(O(N)\)

Sorting and coordinate compression take \(O(N\log N)\). Adding elements to the Fenwick Tree takes \(O(\log N)\) each for \(N\) total insertions, and querying the count also takes \(O(\log N)\) each for \(N\) queries.

Key Implementation Points

• Use 1-based indexing for the Fenwick Tree
  In the code, ranks is used to convert physical strengths into indices starting from \(1\).

• Distinguish between “less than” and “less than or equal to”
  Since we want the number of members with physical strength at least \(Y-b\), what we subtract is the number of members with physical strength strictly less than \(Y-b\). Using bisect_left allows us to correctly keep members whose physical strength is exactly \(Y-b\).

• The return value of binary search can be used directly as the range for the prefix sum
  k = bisect_left(values, Y-b) represents how many distinct values at the beginning of values do not satisfy the condition. Because their indices in the Fenwick Tree range from \(1\) to k, we compute the sum of the first k elements.

• Count members with identical stats individually
  Even when identical physical strength values are grouped together by coordinate compression, each member still adds \(1\) to the Fenwick Tree, so the counts are maintained accurately.

• A large integer type is required for the answer
  The answer can be up to \(\frac{N(N-1)}{2}\), which does not fit in a \(32\)-bit integer. While this is not an issue in Python, a \(64\)-bit integer type should be used in other languages.

  Source Code

import sys
from bisect import bisect_left


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, x, y = data[:3]
    members = list(zip(data[3::2], data[4::2]))
    del data
    members.sort()

    values = sorted({b for _, b in members})
    m = len(values)
    ranks = {b: i + 1 for i, b in enumerate(values)}
    bit = [0] * (m + 1)

    p = n - 1
    inserted = 0
    answer = 0

    for a, b in members:
        threshold = x - a
        while p >= 0 and members[p][0] >= threshold:
            k = ranks[members[p][1]]
            while k <= m:
                bit[k] += 1
                k += k & -k
            inserted += 1
            p -= 1

        k = bisect_left(values, y - b)
        below = 0
        while k:
            below += bit[k]
            k -= k & -k

        answer += inserted - below
        if a + a >= x and b + b >= y:
            answer -= 1

    print(answer // 2)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.