Overview

Given a sequence \(A\) consisting of scores of \(N\) students, the problem asks to find the number of pairs of students whose sum of scores is at least \(K\).

Analysis

A naive approach that exhaustively searches all pairs requires a double loop, resulting in \(O(N^2)\) time complexity. Given the constraint \(N \leq 2 \times 10^5\), this approach would result in a Time Limit Exceeded (TLE) verdict.

Since we only need to count the number of pairs and the original order of elements (student IDs) does not matter, we first consider sorting the array \(A\) in ascending order. On the sorted array, we can use a technique called “Two Pointers,” which examines elements from both ends, to dramatically reduce the time complexity.

For example, suppose the sum of the leftmost element A[left] and the rightmost element A[right] is at least \(K\). Since the array is sorted in ascending order, adding A[right] to elements larger than A[left], such as A[left+1] or A[left+2], will always produce a sum of at least \(K\). In other words, the number of partners that form a pair with A[right] summing to at least \(K\) is right - left people, from index left to right-1, and this can be computed all at once.

Algorithm

1. Sort the student score array \(A\) in ascending order.
2. Set two pointers: left to \(0\) (the beginning of the array) and right to \(N - 1\) (the end of the array), and initialize the count of valid pairs ans to \(0\).
3. Repeat the following operations while left < right:
   • If A[left] + A[right] \geq K: All elements from A[left] to A[right-1] will have a sum of at least \(K\) when paired with A[right]. Therefore, add right - left to ans, and decrement right by \(1\) (to examine the next largest element).
   • If A[left] + A[right] < K: A[right] is the largest element in the current range, but even adding it to A[left] does not reach \(K\), so no more valid pairs can be formed using A[left]. Therefore, increment left by \(1\).
4. Output the final value of ans.

Complexity

• Time complexity: \(O(N \log N)\) Sorting the array takes \(O(N \log N)\). In the subsequent two-pointer phase (the while loop), at each step either left increases or right decreases, so the loop runs at most \(N\) times, giving \(O(N)\). The overall time complexity is \(O(N \log N)\), which comfortably fits within the time limit.
• Space complexity: \(O(N)\) \(O(N)\) memory is used to store the score array \(A\).

Implementation Notes

• Beware of overflow: The maximum possible answer is \(\frac{N(N-1)}{2}\), which occurs when all pairs satisfy the condition. When \(N = 2 \times 10^5\), the answer is approximately \(2 \times 10^{10}\), exceeding the upper limit of 32-bit integers (approximately \(2 \times 10^9\)). In Python, arbitrary-precision integers are used automatically so this is not a concern, but when using C++ or Java, you need to use a 64-bit integer type (such as long long) for the variable storing the answer.

• Fast I/O: Since the number of input values can be large, in Python using fast input methods such as sys.stdin.read().split() can reliably reduce execution time.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(x) for x in input_data[2:]]
    
    A.sort()
    
    ans = 0
    left = 0
    right = N - 1
    
    while left < right:
        if A[left] + A[right] >= K:
            ans += right - left
            right -= 1
        else:
            left += 1
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.