Overview

Given \(N\) members, the problem asks us to efficiently count the total number of ordered pairs \((i, j)\) where member \(i\) is overconfident—meaning their self-evaluation exceeds \(j\)’s rating despite their actual skill (rating) being no greater than \(j\)’s.

Analysis

Organizing the Conditions

The condition for member \(i\) to “look down on” member \(j\) is: - \(C_i > S_j\) (member \(i\)’s self-evaluation is greater than member \(j\)’s rating) - \(S_i \leq S_j\) (member \(i\)’s rating is no greater than member \(j\)’s rating)

Looking at this from the perspective of \(j\), for each \(i\) we want to count the number of \(j\) (\(j \neq i\)) satisfying:

\[S_i \leq S_j < C_i\]

In other words, the number of \(j\) where “\(S_j\) is at least \(S_i\) and less than \(C_i\).”

Key Observations

• If \(C_i \leq S_i\), there is no \(j\) that simultaneously satisfies \(S_j \geq S_i\) and \(S_j < C_i\), so we can skip.
• If \(C_i > S_i\), then \(j = i\) itself satisfies the condition \(S_i \leq S_i < C_i\), so we need to subtract 1 from the count.

Problem with the Naive Approach

Checking all pairs \((i, j)\) takes \(O(N^2)\), which is too slow for \(N \leq 2 \times 10^5\).

Solution

If we sort the values of \(S\), we can determine “how many \(S_j\) values are at least \(S_i\) and less than \(C_i\)” using binary search in \(O(\log N)\).

Algorithm

1. Prepare a sorted array S_sorted of all members’ ratings \(S\).
2. For each member \(i\):
   • If \(C_i \leq S_i\), skip (no \(j\) satisfies the condition).
   • Otherwise, use binary search to find the number of elements in S_sorted within the range \([S_i, C_i)\).
     • lo = bisect_left(S_sorted, S_i) → first position with value at least \(S_i\)
     • hi = bisect_left(S_sorted, C_i) → first position with value at least \(C_i\) (one past the last value less than \(C_i\))
     • The count is hi - lo
   • Subtract 1 to exclude oneself (\(j = i\)).
3. Sum the results for all \(i\) and output.

Concrete Example

For example, with \(N = 3\) and \((S, C) = \{(5, 8), (7, 6), (3, 4)\}\): - S_sorted = [3, 5, 7] - \(i = 1\): \(S_1 = 5, C_1 = 8\). Values of \(S\) in \([5, 8)\) are \(\{5, 7\}\) → 2 elements, subtract self to get 1. - \(i = 2\): \(S_2 = 7, C_2 = 6\). \(C_2 \leq S_2\), so skip. - \(i = 3\): \(S_3 = 3, C_3 = 4\). Values of \(S\) in \([3, 4)\) are \(\{3\}\) → 1 element, subtract self to get 0.

Answer: \(1\)

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, plus \(O(\log N)\) binary search × \(N\) times for each member)
• Space complexity: \(O(N)\) (for storing the sorted array)

Implementation Notes

• By using bisect_left(S_sorted, S_i) and bisect_left(S_sorted, C_i), we can accurately compute the number of elements in the half-open interval \([S_i, C_i)\).

• When \(C_i > S_i\), oneself always satisfies the condition \(S_i \leq S_i < C_i\), so we can always subtract 1 (no case distinction needed).

• Since the input can be large, reading all at once with sys.stdin.buffer.read() improves performance.

  Source Code

import sys
from bisect import bisect_left, bisect_right, insort

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    S = [0] * N
    C = [0] * N
    for i in range(N):
        S[i] = int(input_data[idx]); idx += 1
        C[i] = int(input_data[idx]); idx += 1

    # Count ordered pairs (i, j) where:
    #   C_i > S_j  and  S_i <= S_j  and  i != j
    #
    # For each i, we need count of j such that:
    #   S_j >= S_i  and  S_j < C_i  and  j != i
    #
    # If C_i <= S_i, no valid j exists.
    # Otherwise, count j with S_i <= S_j < C_i, then subtract 1 if i itself satisfies S_i <= S_i < C_i
    # (which is always true when C_i > S_i, so always subtract 1).

    # Sort S values to use binary search
    S_sorted = sorted(S)

    ans = 0
    for i in range(N):
        si = S[i]
        ci = C[i]
        if ci <= si:
            continue
        # Count j with S_j >= si and S_j < ci
        lo = bisect_left(S_sorted, si)
        hi = bisect_left(S_sorted, ci)
        count = hi - lo
        # Subtract 1 for j == i (since si >= si and si < ci is true when ci > si)
        count -= 1
        ans += count

    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.