Overview

We count the number of pairs of club members whose total technical skill is at least \(X\) and whose total physical strength is at least \(Y\). By sorting members by technical skill to manage candidates, we can quickly count how many satisfy the physical strength condition using a Fenwick Tree (BIT).

Analysis

1. Checking all pairs is too slow

An approach that examines all pairs \((i,j)\) has a time complexity of \(O(N^2)\).

When \(N=10^5\), there are about \(50\) billion pairs to check, so this method will not finish within the time limit.

2. Sorting by technical skill means candidates only need to be added

Let a member’s technical skill and physical strength be \((a,b)\). The conditions required for their partner are:

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

Here, we sort the members in ascending order of technical skill and iterate through them in that order.

Since the current member’s technical skill \(a\) never decreases, the partner’s required technical skill \(X-a\) never increases. Therefore, candidates satisfying the technical skill condition are only added and never need to be removed.

For example, when \(X=10\), as the current member’s technical skill increases as \(3,5,7\), the required technical skill for the partner decreases as \(7,5,3\).

Thus, by moving a pointer from the end of the sorted array, we can sequentially add members who satisfy the technical skill condition to a data structure.

3. Counting the physical strength condition with a Fenwick Tree

Among the candidates that satisfy the technical skill condition, we want to find how many also have a physical strength of at least \(Y-b\).

This can be computed by the following subtraction:

\( \text{Number of members satisfying the condition}=\text{Total candidates}-\text{Candidates with physical strength less than }Y-b \)

A Fenwick Tree can add a count at each position and compute the prefix sum from the beginning up to a certain position, each in \(O(\log N)\) time.

However, since physical strength can be up to \(10^9\), we cannot directly use its value as an array index. We apply coordinate compression to replace physical strength values with indices in sorted order, and manage them with the Fenwick Tree.

4. Adjusting for self-pairing and duplicates

In this approach, candidates for a partner are not restricted to “members appearing after oneself.” Therefore, the following adjustments are necessary:

• If the member themselves also satisfies the conditions, subtract that \(1\) person.
• Since pairs of distinct members are counted from both directions, divide by \(2\) at the end.

A member is counted with themselves when \(2a\ge X\) and \(2b\ge Y\).

Algorithm

In the following, indices refer to \(0\)-based indices after sorting members in ascending order of technical skill. Reordering them does not change the pairs of members or their conditions.

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

2. Coordinate-compress the physical strength values.

   • Collect the physical strengths of all members, sort them, and remove duplicates to create an array coordinates.
   • For each member, store the index of their physical strength in this array as b_index.

3. Initialize variables for managing candidates.

   • pointer = N - 1: The index of the next member to add to candidates
   • active = 0: The number of candidates currently added
   • answer = 0: The cumulative count of valid partners
   • Fenwick Tree: Counts the added candidates by their compressed physical strength

4. Process the members in order from the beginning.

Let the current member’s technical skill and physical strength be \((a,b)\).

① Add candidates satisfying the technical skill condition

As long as the member pointed to by pointer satisfies \(A_{\text{pointer}}+a\ge X\), repeat the following:

• Add \(1\) at the position corresponding to that member’s physical strength in the Fenwick Tree.
• Increment active by \(1\).
• Decrement pointer by \(1\).

Because the array is sorted, by the end of this process, exactly all members satisfying the technical skill condition will have been added.

② Add the number of candidates that also satisfy the physical strength condition

Using lower_bound, let below be the first index in coordinates where the value is at least \(Y-b\).

Then, compressed indices strictly less than below correspond exactly to physical strengths less than \(Y-b\). Therefore, add

active - fenwick.prefix_sum(below)

to answer.

For example, if coordinates is \([2,5,8]\) and the required physical strength is \(6\), below is \(2\). Subtracting the number of candidates with physical strength \(2,5\) from the total candidates gives the number of candidates with physical strength \(6\) or greater.

③ Exclude oneself

If \(2a\ge X\) and \(2b\ge Y\), the member themselves was included in the count above, so subtract \(1\) from answer.

1. Output answer / 2.

Each valid pair of distinct members has been counted twice—once when focusing on one member and once on the other. Therefore, dividing by \(2\) gives the desired number of pairs.

Complexity

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

Sorting and coordinate compression take \(O(N\log N)\) time. Since pointer only decreases, candidate additions via the while loop occur at most \(N\) times in total. Each addition as well as the query and summation for each member can be processed in \(O(\log N)\) time.

Implementation Notes

• Use a 64-bit integer for the answer
  The number of pairs can be up to \(\frac{N(N-1)}{2}\), which exceeds the range of a 32-bit integer. Furthermore, the accumulated sum before dividing by \(2\) at the end also grows large, so answer should be a long long.

• Be careful with the range definition of the Fenwick Tree
  In this code, prefix_sum(count) returns the sum over compressed indices in the range from \(0\) up to (but not including) count. Therefore, prefix_sum(below) gives the number of candidates with physical strength less than \(Y-b\).

• Use lower_bound to include boundary values
  We need the number of members with physical strength at least \(Y-b\). Make sure not to exclude members with physical strength exactly \(Y-b\). For technical skill as well, the comparison is >=.

• Members with the same physical strength are each added as 1 person
  Coordinate compression maps identical values to the same index, but since we add \(1\) to the Fenwick Tree for each member, the count is maintained correctly.

• Only exclude oneself when both conditions are satisfied
  If oneself satisfies only the technical skill condition or only the physical strength condition, they were not counted in the first place, so do not subtract them.

  Source Code

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

class FenwickTree {
    int n;
    vector<int> bit;

public:
    explicit FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    void add(int index) {
        for (++index; index <= n; index += index & -index) {
            ++bit[index];
        }
    }

    int prefix_sum(int count) const {
        int result = 0;
        for (; count > 0; count -= count & -count) {
            result += bit[count];
        }
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long X, Y;
    cin >> N >> X >> Y;

    vector<pair<long long, long long>> members(N);
    vector<long long> coordinates;
    coordinates.reserve(N);

    for (auto& [a, b] : members) {
        cin >> a >> b;
        coordinates.push_back(b);
    }

    sort(members.begin(), members.end());
    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()),
                      coordinates.end());

    vector<int> b_index(N);
    for (int i = 0; i < N; ++i) {
        b_index[i] = lower_bound(coordinates.begin(), coordinates.end(),
                                 members[i].second) - coordinates.begin();
    }

    FenwickTree fenwick(static_cast<int>(coordinates.size()));
    int pointer = N - 1;
    int active = 0;
    long long answer = 0;

    for (int i = 0; i < N; ++i) {
        const auto [a, b] = members[i];

        while (pointer >= 0 && members[pointer].first + a >= X) {
            fenwick.add(b_index[pointer]);
            ++active;
            --pointer;
        }

        int below = lower_bound(coordinates.begin(), coordinates.end(), Y - b)
                    - coordinates.begin();
        answer += active - fenwick.prefix_sum(below);

        if (2 * a >= X && 2 * b >= Y) {
            --answer;
        }
    }

    cout << answer / 2 << '\n';
    return 0;
}

---

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