Overview

For each student’s score \(A_i\), we count how many students have “at least one” other student whose score differs by exactly \(K\) in absolute value.

Analysis

A naive approach would check all pairs \((i, j)\) (\(i \neq j\)) to see if \(|A_i-A_j|=K\), but this is \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).

The key observations are as follows:

• What we want is not “the number of pairs satisfying the condition” but “the number of students satisfying the condition.”
• Focusing on the scores themselves, for student \(i\) to satisfy the condition, it suffices that there exists another student with a score of \(A_i + K\) or \(A_i - K\).
• Since multiple students can have the same score, we can improve efficiency by counting the frequency (number of occurrences) of each score.

The case \(K=0\) requires special attention.
Since \(|A_i-A_j|=0\), we need “a different person with the same score.” In other words, if score \(x\) appears \(2\) or more times, then all students with that score satisfy the condition (a score appearing only once does not satisfy it).

Example: \(A=[10,10,12]\), \(K=0\)
Score 10 has 2 students, so those 2 satisfy the condition, but 12 has only 1 student so it does not → the answer is 2.

Algorithm

1. For the score array \(A\), count the frequency of each score using a Counter (associative array).
2. Case distinction:
   • When \(K=0\):
     For each score with a frequency of \(2\) or more, add that frequency to the answer.
     (Since a partner with the same score exists, all students with that score satisfy the condition.)
   • When \(K>0\):
     For each score \(x\) (with frequency \(v\)), if \(x+K\) or \(x-K\) exists in cnt, then all \(v\) students with that score satisfy the condition, so add \(v\) to the answer.

This way, instead of searching for a partner for each student, we can determine the answer by checking existence per score (\(O(1)\) expected).

Complexity

• Time complexity: \(O(N)\) (Counter creation is \(O(N)\), and iterating over the distinct scores is \(O(M)\) where \(M \le N\))
• Space complexity: \(O(N)\) (to store the frequency of each score)

Implementation Notes

• Always handle \(K=0\) separately (because \(x+K\) and \(x-K\) become the same value, making it impossible to correctly handle the “someone other than oneself” requirement).

• Using a Counter allows fast checking of “whether score \(y\) exists” via y in cnt.

• Since the input can have up to \(2\times 10^5\) elements, we use sys.stdin.buffer.read() for bulk reading to speed up input.

  Source Code

import sys
from collections import Counter

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    cnt = Counter(A)

    if K == 0:
        ans = sum(v for v in cnt.values() if v >= 2)
    else:
        ans = 0
        for x, v in cnt.items():
            if (x + K) in cnt or (x - K) in cnt:
                ans += v

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.