Overview

This problem asks us to efficiently count the total number of pairs \((i, j)\) satisfying the given condition “\(S_i \leq S_j < C_i\) and \(i \neq j\)”.

Analysis

Naive Approach and Its Limitations

If we naively check whether the condition is satisfied for every pair \((i, j)\), we end up with a nested loop resulting in \(O(N^2)\) time complexity. Since \(N \le 2 \times 10^5\) in this problem, the worst case requires approximately \(4 \times 10^{10}\) operations, which exceeds the time limit and results in TLE (Time Limit Exceeded). Therefore, a faster approach is needed.

Organizing the Conditions and Ideas for Speedup

Let’s fix member \(i\) as the subject and think about how to quickly count how many other members \(j\) satisfy the condition. The conditions for member \(i\) to look down on member \(j\) are as follows: 1. \(i \neq j\) 2. \(S_i \leq S_j < C_i\)

Here, we consider cases based on the relationship between \(S_i\) and \(C_i\) for each \(i\).

• When \(C_i \le S_i\) No \(S_j\) satisfies \(S_i \le S_j < C_i\) (because the lower bound is greater than or equal to the upper bound). Therefore, member \(i\) looks down on \(0\) people.

• When \(C_i > S_i\) We search for \(j\) satisfying \(S_i \le S_j < C_i\). This range always includes oneself (\(j = i\)) (since \(S_i \le S_i < C_i\) holds). However, due to the condition \(i \neq j\), we must exclude oneself. Therefore, the number of members that member \(i\) looks down on is obtained by counting how many ratings among all members satisfy \(S_i \le S_j < C_i\), then subtracting \(1\) for oneself.

“The number of elements within a certain range (greater than or equal to \(S_i\) and less than \(C_i\))” can be efficiently computed using binary search by sorting the array of ratings beforehand.

Algorithm

1. Create an array \(A\) by sorting all members’ ratings \(S\) in ascending order.
2. Initialize a variable ans to \(0\) to store the answer.
3. For each member \(i\) (\(1 \le i \le N\)), perform the following steps:
   • Only proceed if \(C_i > S_i\).
   • Using binary search (bisect_left), find the number of elements in array \(A\) with values less than \(C_i\). Call this \(R\).
   • Using binary search, find the number of elements in array \(A\) with values less than \(S_i\). Call this \(L\).
   • The number of ratings in the half-open interval \([S_i, C_i)\) is \(R - L\).
   • Add \(R - L - 1\) (subtracting oneself) to ans.
4. Output the final value of ans.

Explanation with a Concrete Example

Let \(S = [2, 5, 12]\), \(C = [10, 3, 15]\). The sorted array is \(A = [2, 5, 12]\).

• Member 1 (\(S_1=2, C_1=10\)): Since \(C_1 > S_1\), we perform the search.
  • Number of elements less than \(10\): \(2\) (\(2, 5\)) \(\to R = 2\)
  • Number of elements less than \(2\): \(0\) \(\to L = 0\)
  • \(R - L - 1 = 2 - 0 - 1 = 1\) person (looking down on Member 2)
• Member 2 (\(S_2=5, C_2=3\)): Since \(C_2 \le S_2\), we skip (\(0\) people).
• Member 3 (\(S_3=12, C_3=15\)): Since \(C_3 > S_3\), we perform the search.
  • Number of elements less than \(15\): \(3\) (\(2, 5, 12\)) \(\to R = 3\)
  • Number of elements less than \(12\): \(2\) (\(2, 5\)) \(\to L = 2\)
  • \(R - L - 1 = 3 - 2 - 1 = 0\) people.

The total is \(1 + 0 + 0 = 1\) pair.

Complexity

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

  • Sorting the rating array \(S\) takes \(O(N \log N)\).
  • Binary search (bisect_left) for each member is \(O(\log N)\), and performing this \(N\) times gives \(O(N \log N)\) overall.
  • When \(N = 2 \times 10^5\), we have approximately \(N \log N \approx 3.6 \times 10^6\) operations, which comfortably fits within the time limit (typically 2 seconds).

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

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

Implementation Notes

• Excluding Oneself: When \(C_i > S_i\), the count obtained by binary search always includes oneself (\(S_i\)), so we must always subtract 1 at the end. Forgetting this step results in counting oneself as being looked down upon (a self-contradictory count), leading to WA (Wrong Answer).

• Binary Search Library: In Python, using bisect_left from the bisect module allows us to concisely obtain the number of elements less than a specified value in \(O(\log N)\).

  Source Code

import sys
from bisect import bisect_left

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    
    S = [0] * N
    C = [0] * N
    for i in range(N):
        S[i] = int(data[2 * i + 1])
        C[i] = int(data[2 * i + 2])
    
    A = sorted(S)
    
    ans = 0
    for i in range(N):
        si = S[i]
        ci = C[i]
        if ci > si:
            idx_S = bisect_left(A, si)
            idx_C = bisect_left(A, ci)
            ans += idx_C - idx_S - 1
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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