Overview

Given an array of each student’s scores, perform \(M\) “overwrite the value at a specified position” operations, and finally count the number of students with scores less than \(K\).

Analysis

Since the updates are “replacements (assignments)” rather than “additions,” the scores after all updates are complete can be represented simply by an array \(Q\) with the updates applied in order. Therefore, the only things we need to do are:

1. Prepare the initial array \(Q\)
2. For each update \((P_j, V_j)\), perform \(Q[P_j] \leftarrow V_j\)
3. Count the number of elements in the final \(Q\) that satisfy \(x < K\)

Here, if we naively “recount the number of students needing supplementary lessons after every update,” it takes \(O(N)\) per count, resulting in \(O(NM)\) total. With a maximum of \(N=M=10^5\), this would be on the order of \(10^{10}\) operations, which won’t finish in time (TLE).

However, since this problem only asks for the “final result,” there’s no need to recount during updates. It’s sufficient to apply all updates and then count just once at the end.

(Example)
When \(N=3, K=60, Q=[70,50,80]\), with update \((2,65)\):
After the update, \(Q=[70,65,80]\), and we just count that there are 0 people with scores less than \(60\).

Algorithm

1. Read \(N,M,K\)
2. Read the array \(Q\) of length \(N\)
3. Repeat the following \(M\) times:
   • Read \(p,v\)
   • Since input \(p\) is 1-indexed, convert to \(p-1\) and overwrite \(Q[p-1] = v\)
4. Finally, count and output the number of elements in \(Q\) satisfying \(x < K\)

Complexity

• Time complexity: \(O(N+M)\) (\(M\) updates and a final count over \(N\) elements)
• Space complexity: \(O(N)\) (storing the score array \(Q\))

Implementation Notes

• Student numbers \(P_j\) are 1-indexed, so always convert to \(P_j-1\) when accessing the array.

• Since the input size can be up to around \(2\times 10^5\), in Python it is faster to read all input at once using sys.stdin.buffer.read() and process it with split().

• Since \(M=0\) is possible, make sure the code works correctly even when the update loop runs 0 times.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    Q = [next(it) for _ in range(N)]

    for _ in range(M):
        p = next(it) - 1
        v = next(it)
        Q[p] = v

    ans = sum(1 for x in Q if x < K)
    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.