Overview

This problem asks you to efficiently count the total number of “looking down on” pairs \((i, j)\), where member \(i\)’s actual ability (rating) is at most that of member \(j\), yet member \(i\) overestimates themselves and believes they surpass member \(j\)’s ability. The solution uses binary search for efficient computation.

Analysis

1. Naive Approach and Its Limitations

Consider a naive approach that checks whether the condition is satisfied for every pair \((i, j)\) (brute-force search using nested loops). This approach requires \(O(N^2)\) time complexity. Since \(N \le 2 \times 10^5\) in this problem, this would require approximately \(4 \times 10^{10}\) operations in the worst case, which exceeds the time limit (typically 2 seconds) and results in TLE (Time Limit Exceeded).

Therefore, a more efficient approach is needed.

2. Organizing the Conditions

When we fix member \(i\), the conditions for member \(i\) to be “looking down on” member \(j\) are: 1. \(i \neq j\) 2. \(C_i > S_j\) 3. \(S_i \le S_j\)

Combining these, the condition is equivalent to member \(j\)’s rating \(S_j\) being in the following range: - \(S_i \le S_j < C_i\) (and \(j \neq i\))

In other words, if we can efficiently count “the number of ratings among all members that are at least \(S_i\) and less than \(C_i\)” for each \(i\), we can solve this problem.

3. Speeding Up with Binary Search

We prepare a sorted array \(A\) of all members’ ratings in advance. For a sorted array, we can use binary search (lower_bound) to find the number of elements within a specific range in \(O(\log N)\).

Specifically, for each \(i\), we process as follows:

• When \(S_i \ge C_i\): No \(S_j\) can satisfy \(S_i \le S_j < C_i\), so the count is \(0\).
• When \(S_i < C_i\): We use binary search on the sorted array \(A\) to find the number of elements in the half-open interval \([S_i, C_i)\).
  • The position of the smallest element that is at least \(C_i\) (lower_bound(A.begin(), A.end(), C[i]))
  • The position of the smallest element that is at least \(S_i\) (lower_bound(A.begin(), A.end(), S[i]))

We compute the difference between these two positions (number of elements). However, this range includes \(S_i\) itself (since \(S_i < C_i\), the member themselves satisfies \(S_i \le S_i < C_i\)). Because the problem requires \(i \neq j\), we subtract \(1\) (for the member themselves) from the computed count and add the result to the answer.

Algorithm

1. Read the input and store the rating array \(S\) and the self-assessment array \(C\).
2. Create an array \(A\) as a copy of \(S\) and sort it in ascending order.
3. Initialize the variable ans to \(0\) to store the answer.
4. For each \(i = 0, 1, \dots, N-1\), repeat the following:
   • If \(S_i \ge C_i\), do nothing and proceed to the next iteration.
   • If \(S_i < C_i\):
     • Use binary search to find the number of elements count in array \(A\) that are at least \(S_i\) and less than \(C_i\).
     • Add count - 1 to ans.
5. Output the final value of ans.

Complexity

• Time Complexity: \(O(N \log N)\)

  • Sorting the rating array takes \(O(N \log N)\).
  • The binary search (lower_bound) for each member \(i\) takes \(O(\log N)\), and since this is performed \(N\) times, the total search cost is \(O(N \log N)\).
  • Overall, the complexity is \(O(N \log N)\), which is well within the time limit even for \(N = 2 \times 10^5\).

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used to store the input data and the sorted array \(A\).

Implementation Notes

• Type Considerations (Preventing Overflow) In the extreme case where everyone looks down on everyone else, the maximum value of the answer reaches \(N(N-1) \approx 4 \times 10^{10}\). This exceeds the maximum value of a 32-bit integer type (such as int in C++, approximately \(2 \times 10^9\)), so the variable ans that holds the answer must use a 64-bit integer type (long long).

• Fast I/O Since \(N\) can be large, in C++ it is recommended to speed up input/output using cin.tie(NULL) and ios_base::sync_with_stdio(false).

  Source Code

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

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> S(N), C(N);
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i] >> C[i];
        A[i] = S[i];
    }

    // レーティングをソートして二分探索できるようにする
    sort(A.begin(), A.end());

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        // S_i >= C_i の場合、S_i <= S_j < C_i を満たす S_j は存在しない
        if (S[i] >= C[i]) {
            continue;
        }

        // A の中で [S_i, C_i) の範囲にある要素の個数を二分探索で求める
        auto it1 = lower_bound(A.begin(), A.end(), C[i]);
        auto it2 = lower_bound(A.begin(), A.end(), S[i]);
        long long count = distance(it2, it1);

        // S_i < C_i であるため、自分自身 (j = i) がカウントに含まれている。
        // i != j の条件を満たすため、1 を引く。
        ans += count - 1;
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.