Overview

Given a score array \(A\), choose 2 distinct people \((i,j)\) and count the number of pairs satisfying \(A_i + A_j \ge K\). We efficiently count all pairs using sort + two pointers.

Analysis

A naive approach would check all pairs \((i,j)\) (\(1 \le i < j \le N\)), with time complexity \(O(N^2)\). However, since \(N \le 2 \times 10^5\), this results in up to about \(2 \times 10^{10}\) pairs, which is far too slow (TLE).

The key observations are the following two points:

• When scores are sorted in ascending order, the magnitude relationship of “small value + large value” becomes monotonic.
• For a given right-end element \(A[r]\), if \(A[l] + A[r] \ge K\) holds, then for all \(i\) to the right of \(l\) (\(l < i < r\)), since \(A[i] \ge A[l]\), we have
  \(A[i] + A[r] \ge A[l] + A[r] \ge K\), which always holds.

In other words, instead of checking each pair one by one, we can “count them all at once.”

Example: \(A=[1,3,4,8]\) (sorted), \(K=10\)
With \(r=3\) (value 8), \(l=1\) (value 3), if \(3+8 \ge 10\), then not only \((1,3)\) but also \((2,3)\) (\(4+8\)) certainly satisfies the condition, so we can count 2 pairs at once.

Algorithm

1. Sort the array \(A\) in ascending order.
2. Prepare two pointers \(l=0\) (left end), \(r=N-1\) (right end).
3. While \(l<r\), repeat the following:
   • If \(A[l] + A[r] \ge K\):
     With \(r\) fixed, all candidates on the left side \(l, l+1, \dots, r-1\) satisfy the condition.
     Therefore, add \((r-l)\) to the pair count, then decrement \(r\) by 1 (\(r \leftarrow r-1\)).
   • Otherwise (\(A[l] + A[r] < K\)):
     With this \(l\), no matter how far right we choose (the rightmost being \(r\)), the condition cannot be satisfied, so increment \(l\) by 1 (\(l \leftarrow l+1\)).
4. The accumulated total is the answer.

In this method, each pointer moves in one direction at most \(N\) times, so the part after sorting runs in \(O(N)\).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting; the two-pointer part is \(O(N)\))
• Space complexity: \(O(N)\) (to store the array)

Implementation Notes

• The crucial point is that when the condition \(A[l] + A[r] \ge K\) is satisfied, we add “\((r-l)\)” rather than “1” (counting in bulk).

• To maintain \(l<r\) (ensuring the same student is not used twice), the loop condition should be while l < r:.

• The answer can be as large as \(\binom{N}{2}\), so depending on the language, 64-bit integers may be necessary (in Python, this is handled automatically).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    k = int(data[1])
    a = list(map(int, data[2:2+n]))
    a.sort()

    l, r = 0, n - 1
    ans = 0
    while l < r:
        if a[l] + a[r] >= k:
            ans += (r - l)
            r -= 1
        else:
            l += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.