Official

E - ペアの選定 / Choosing Pairs Editorial by admin

Gemini 3.8 Flash (High)

Overview

This problem asks us to find the number of pairs \((i, j)\) (\(i < j\)) among \(N\) club members such that \(A_i + A_j \ge X\) and \(B_i + B_j \ge Y\). It can be reduced to the problem of counting the number of points in a 2D region, which can be solved efficiently using a plane sweep and a Fenwick Tree (Binary Indexed Tree).

Analysis

Naive Approach and Its Limitations

First, one might consider checking whether the condition holds for all pairs \((i, j)\) (\(\frac{N(N-1)}{2}\) pairs in total). However, given the constraint \(N \le 10^5\), the number of pairs is roughly \(5 \times 10^9\). This will far exceed the time limit (typically 2 to 3 seconds) and result in TLE (Time Limit Exceeded). Therefore, we need an efficient algorithm that runs in about \(O(N \log N)\) time.

Rephrasing as a Geometric Problem

Let us rearrange the condition inequalities. If we fix a club member \(i\), the partner member \(j\) must satisfy the following two conditions: - \(A_j \ge X - A_i\) - \(B_j \ge Y - B_i\)

If we treat each member \(j\) as a point \((A_j, B_j)\) on a 2D plane, this turns into a 2D range query: “Count the number of points \((A_j, B_j)\) such that \(x \ge X - A_i\) and \(y \ge Y - B_i\).”

Although the problem asks for all pairs, we can solve the original problem by counting the number of valid partners \(j\) for each member \(i\), and then compensating for duplicates (the ordering of \(i\) and \(j\), as well as the self-pair where \(i = j\)) afterwards.

Using a Plane Sweep (Sweep-line Algorithm)

Since handling two-dimensional conditions simultaneously is difficult, we apply the plane sweep method, where we process one dimension (\(x\)-coordinate) by sorting events and manage the other dimension (\(y\)-coordinate) using a data structure.

  1. Sweep through the \(x\)-coordinates in descending order (from largest to smallest).
  2. Prepare two types of events: adding a point \((A_j, B_j)\) and evaluating a query \((X - A_i, Y - B_i)\).
  3. By processing events in descending order of their \(x\)-coordinates, we ensure that the data structure contains only points whose \(x\)-coordinates are greater than or equal to that of the current query.
  4. Then, the data structure only needs to quickly query the number of points with \(y\)-coordinates greater than or equal to \(Y - B_i\).

Since the values of the \(y\)-coordinates can be up to \(2 \times 10^9\) (which is very large), we can apply coordinate compression to all appearing values beforehand. Using a Fenwick Tree, we can add values and query range sums in \(O(\log N)\) time per operation.

Algorithm

  1. Coordinate Compression:

    • There are at most \(2N\) distinct values relevant to the \(y\)-coordinates: \(B_i\) and \(Y - B_i\) for each member. Sort these values in ascending order, remove duplicates, and assign each value a 1-based rank (ID).

  2. Creating and Sorting Events:

    • Point Addition Event: For member \(j\), \((x = A_j, \text{type} = \text{point}, y\text{ ID} = \text{id}(B_j))\)
    • Query Event: For member \(i\), \((x = X - A_i, \text{type} = \text{query}, y\text{ ID} = \text{id}(Y - B_i), \text{member index} = i)\)
    • Sort these \(2N\) events in descending order of their \(x\)-coordinates.
    • Note: If \(x\)-coordinates are equal, points must be added before queries are processed. Therefore, process “point” events before “query” events.

  3. Sweeping and Processing Queries:

    • Initialize an empty Fenwick Tree.
    • Process the sorted events from start to finish:
      • Point Addition Event: Add \(+1\) at the position corresponding to the point’s \(y\) ID.
      • Query Event: Use the Fenwick Tree to query the total count of points in the range \([y\text{ ID}, \text{max ID}]\), and record this as the number of partner candidates \(cnt[i]\) for member \(i\).

  4. Removing Duplicates and Computing the Final Answer:

    • The calculated \(cnt[i]\) may include the member themselves (\(j = i\)). If \(2A_i \ge X\) and \(2B_i \ge Y\), member \(i\) has been counted as their own partner, so subtract \(1\) from \(cnt[i]\).
    • When summing \(cnt[i]\) over all \(i\), each valid pair \((i, j)\) has been counted twice (as \((i, j)\) and \((j, i)\)). Therefore, output the total sum divided by \(2\).

Complexity

  • Time Complexity: \(O(N \log N)\)
    • Sorting for coordinate compression: \(O(N \log N)\)
    • Sorting events: \(O(N \log N)\)
    • Sweeping events and Fenwick Tree operations (\(2N\) operations, each \(O(\log N)\)): \(O(N \log N)\)
    • Overall, the time complexity is \(O(N \log N)\), which easily passes within the time limit.
  • Space Complexity: \(O(N)\)
    • The memory required for the event array, Fenwick Tree, coordinate compression array, etc., is \(O(N)\) elements in total.

Implementation Notes

  • Tie-breaking (Order of Operations):

    • When \(x\)-coordinates are equal (e.g., \(A_j = X - A_i\)), because the problem condition includes equality (\(A_i + A_j \ge X\)), point additions must be performed before query processing. Ensure that the comparison function sets the priority of type appropriately when sorting events.

  • Watch Out for Integer Overflow:

    • Since \(X, Y, A_i\), and \(B_i\) can be up to \(10^9\) or \(2 \times 10^9\), use a 64-bit integer type (long long in C++) for the self-pair check 2 * A[i] >= X and for computing the total sum of pairs.

      Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
struct Fenwick {
    int n;
    vector<T> tree;
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
    void add(int i, T delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    T query(int i) {
        T sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
    T query(int l, int r) {
        if (l > r) return 0;
        return query(r) - query(l - 1);
    }
};

struct Event {
    long long x;
    int type; // 1: point, 0: query
    int y_id;
    int id;
};

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

    int n;
    long long x_req, y_req;
    if (!(cin >> n >> x_req >> y_req)) return 0;

    vector<long long> a(n), b(n);
    vector<long long> vals;
    vals.reserve(2 * n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        vals.push_back(b[i]);
        vals.push_back(y_req - b[i]);
    }

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get_id = [&](long long v) {
        return lower_bound(vals.begin(), vals.end(), v) - vals.begin() + 1;
    };

    int m = vals.size();
    vector<Event> events;
    events.reserve(2 * n);

    for (int i = 0; i < n; ++i) {
        events.push_back({a[i], 1, get_id(b[i]), -1});
        events.push_back({x_req - a[i], 0, get_id(y_req - b[i]), i});
    }

    sort(events.begin(), events.end(), [](const Event& e1, const Event& e2) {
        if (e1.x != e2.x) return e1.x > e2.x;
        return e1.type > e2.type;
    });

    Fenwick<int> ft(m);
    vector<int> cnt(n, 0);

    for (const auto& e : events) {
        if (e.type == 1) {
            ft.add(e.y_id, 1);
        } else {
            cnt[e.id] = ft.query(e.y_id, m);
        }
    }

    long long total_pairs = 0;
    for (int i = 0; i < n; ++i) {
        if (2LL * a[i] >= x_req && 2LL * b[i] >= y_req) {
            cnt[i]--;
        }
        total_pairs += cnt[i];
    }

    cout << total_pairs / 2 << "\n";

    return 0;
}

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