Overview

Given the scores of \(N\) students, we need to find the number of pairs when pairing any two students such that the sum of their scores is at least the threshold value \(K\).

Analysis

This problem can be solved by checking whether \(A_i + A_j \geq K\) for all pairs \((i, j)\) (\(i < j\)), but that approach has a time complexity of \(O(N^2)\), which is not practical since \(N\) can be up to \(2 \times 10^5\) (it would result in TLE).

Therefore, we consider sorting the array first. By sorting, we can efficiently determine “for a given student \(i\), which students \(j\) after them can form a pair that satisfies the condition.”

Specifically, when student \(i\) has a score of \(A_i\), the partner’s score \(A_j\) must be at least \(K - A_i\). If we can use binary search on the sorted array to find the smallest \(j\) (\(j > i\)) that satisfies this condition, then all students after that \(j\) can also form valid pairs, allowing us to count efficiently.

Algorithm

1. Sort the student score list \(A\) in ascending order.
2. For each student \(i\) (from \(0\) to \(N-2\)), do the following:
   • Minimum required score for the partner: target = K - A[i]
   • Use binary search (bisect_left) to find the smallest index with a value greater than or equal to this target, searching in the range from \(A[i+1]\) onward.
   • The number of people from the found index pos to the end (i.e., \(N - \text{pos}\)) is the number of students who can form a valid pair with student \(i\).
3. Sum the results for each \(i\) to get the answer.

Example

Consider the following input:

N = 5, K = 7
A = [1, 3, 5, 6, 8]

After sorting, it remains the same: [1, 3, 5, 6, 8]

• \(i=0\) (score 1): Partner needs score 6 or more → 6, 8 → 2 people
• \(i=1\) (score 3): Partner needs score 4 or more → 5, 6, 8 → 3 people
• \(i=2\) (score 5): Partner needs score 2 or more → 5, 6, 8 → 3 people
• \(i=3\) (score 6): Partner needs score 1 or more → 6, 8 → 2 people
• \(i=4\) (score 8): No more partners available → 0 people

Total: 2 + 3 + 3 + 2 + 0 = 10

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, \(O(N \log N)\) for the loop + binary search)
• Space complexity: \(O(1)\) (no extra space used beyond the input)

Implementation Notes

• The array must be sorted.

• The binary search range must start from the next index after the current index \(i\) (i.e., \(i+1\) onward), since a student cannot be paired with themselves.

• Python’s bisect.bisect_left returns the position where the target value should be inserted within the specified range, which gives us the smallest index that satisfies the condition.

  Source Code

import bisect

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

count = 0
for i in range(N):
    # A[i] + A[j] >= K となる最小の j を二分探索で求める
    target = K - A[i]
    # i+1 以降のインデックスで target 以上の要素の位置を探す
    pos = bisect.bisect_left(A, target, i + 1)
    count += N - pos

print(count)

---

This editorial was generated by qwen3-coder-480b.