概要

各生徒の点数配列に対して \(M\) 回の「指定位置の値の上書き」を行い、最後に \(K\) 点未満の人数を数える問題です。

考察

更新は「加算」ではなく「書き換え（代入）」なので、全ての更新が終わった時点の点数は、単にその更新を順に反映した配列 \(Q\) で表せます。したがって、やるべきことは以下の2つだけです。

1. 初期配列 \(Q\) を用意する
   
2. 各更新 \((P_j, V_j)\) について \(Q[P_j] \leftarrow V_j\) を行う
   
3. 最終的な \(Q\) の中で \(x < K\) を満たす要素数を数える

ここで、素朴に「毎回の更新後に補習対象人数を数え直す」と、1回数えるのに \(O(N)\) かかり、合計で \(O(NM)\) になってしまいます。最大で \(N=M=10^5\) なので \(10^{10}\) 回規模となり、時間内に終わりません（TLE）。

しかし本問は「最終結果だけ」を求めればよいので、更新中に人数を数え直す必要がありません。すべての更新を反映してから、最後に1回だけ数えれば十分です。

（例）
\(N=3, K=60, Q=[70,50,80]\)、更新 \((2,65)\) のとき
更新後 \(Q=[70,65,80]\) となり、最後に \(60\) 未満は 0 人、と数えればよいです。

アルゴリズム

1. \(N,M,K\) を読む
2. 長さ \(N\) の配列 \(Q\) を読む
3. \(M\) 回、次を繰り返す
   
   • \(p,v\) を読む
     
   • 入力の \(p\) は \(1\) 始まりなので \(p-1\) に直し、\(Q[p-1] = v\) と上書きする
4. 最後に \(Q\) のうち \(x < K\) を満たす要素数を数えて出力する

計算量

• 時間計算量: \(O(N+M)\)（更新 \(M\) 回と最後のカウント \(N\) 回）
• 空間計算量: \(O(N)\)（点数配列 \(Q\) を保持）

実装のポイント

• 生徒番号 \(P_j\) は \(1\) 始まりなので、配列アクセスでは必ず \(P_j-1\) に変換します。

• 入力サイズが最大 \(2\times 10^5\) 程度あるため、Python では sys.stdin.buffer.read() でまとめて読み、split() して処理すると高速です。

• \(M=0\) の場合もあるので、更新ループが0回でも正しく動くようにします。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。