Overview

For each member \(i\), count the number of opponents \(j\) such that “the opponent’s skill \(S_j\) is at least as high as mine (\(S_i \le S_j\)), yet my self-evaluation \(C_i\) rates myself above them (\(C_i > S_j\)).” Sum this count across all members.

Analysis

The “looking down on” condition: - \(i \ne j\) - \(C_i > S_j\) - \(S_i \le S_j\)

Combined, the opponent \(j\)’s rating \(S_j\) must satisfy:

[ S_i \le S_j < C_i ]

In other words, what we need for each \(i\) is simply “the number of people whose \(S_j\) falls within a certain interval” — the opponent’s self-evaluation \(C_j\) is completely irrelevant.

Why the Naive Approach Fails

Checking all \(j\) for each \(i\) is \(O(N^2)\).
Since \(N \le 2\times 10^5\), this would require up to approximately \(4\times 10^{10}\) comparisons, which is not feasible in time.

How to Solve It

What we need is “the count of values \(S_j\) that fall within the interval \([S_i, C_i)\).” If we sort all values of \(S\) beforehand, we can use binary search to find:

• The first position where \(S_j \ge S_i\)
• The first position where \(S_j \ge C_i\)

The difference gives us the count within the interval.

Additionally, due to the \(i \ne j\) condition, when \(C_i > S_i\), the person themselves (\(S_i\)) is always included in the interval, so we simply subtract 1 at the end.

Algorithm

1. Prepare the rating array \(S\) for all members, and create a sorted copy sortedS.
2. For each member \(i\), do the following:
   • If \(C_i \le S_i\), the interval \([S_i, C_i)\) is empty (or invalid), so skip with a count of 0.
   • Otherwise, use binary search to find:
     • \(l =\) lower_bound(sortedS, S_i) (the first index where \(S_j \ge S_i\))
     • \(r =\) lower_bound(sortedS, C_i) (the first index where \(S_j \ge C_i\))
   • The number of people in the interval \([S_i, C_i)\) is \(r-l\).
   • However, since the person themselves is always counted when \(C_i > S_i\), add \(r-l-1\) to the answer.
3. Output the total.

(Example) \(S=[3,5,7,7]\), for a person with \((S_i,C_i)=(5,8)\):
The interval is \([5,8)\), so the matching \(S_j\) values are \(5,7,7\) — 3 people. Excluding themselves (\(S=5\)), we add 2 pairs.

Complexity

• Time complexity: \(O(N\log N)\) (sorting \(O(N\log N)\) + binary search \(O(\log N)\) for each of \(N\) people)
• Space complexity: \(O(N)\) (rating array and sorted array)

Implementation Notes

• In Python, bisect_left works the same as lower_bound.

• When \(C_i \le S_i\), the result is always 0, so using continue early is safe and clear.

• The -1 in ans += (r - l) - 1 is for “excluding oneself” due to the \(i \ne j\) condition. Even if there are other people with the same rating, subtracting exactly 1 is correct.

  Source Code

import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N = int(input())
    S = []
    C = []
    for _ in range(N):
        s, c = map(int, input().split())
        S.append(s)
        C.append(c)

    sortedS = sorted(S)
    ans = 0

    for s, c in zip(S, C):
        if c <= s:
            continue
        l = bisect_left(sortedS, s)   # first index with Sj >= s
        r = bisect_left(sortedS, c)   # first index with Sj >= c (i.e., Sj < c)
        cnt = r - l
        ans += cnt - 1  # exclude j = i (since s < c, i is counted)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.