概要

各倉庫の最終的な荷物量は「初期量 \(W_i\) に対して、その倉庫に行われた増減の合計を足したもの」なので、全作業後に \(W_i > L_i\) となる倉庫数を数えます。

考察

重要な観察は、知りたいのは「途中経過」ではなく「すべての作業が終わったあとの最終状態」だけだという点です。
作業 \(j\) は倉庫 \(P_j\) の荷物量に \(C_j\) を加える（負なら減る）だけなので、倉庫ごとに増減を累積していけば最終量が求まります。

素朴に「毎回すべての倉庫を見直して、溢れている個数を数え直す」と、各作業ごとに \(O(N)\) かかり、合計で \(O(NM)\) となってしまい最大で \(4 \times 10^{10}\) 程度になりTLEします。
しかしこの問題では、各作業で変化するのは「対象の倉庫1つだけ」なので、その倉庫の値に加算していき、最後に一度だけ全倉庫をチェックすれば十分です。

（例）倉庫1の初期が \(W_1=5\)、作業で \(+3, -2\) が入るなら最終は \(5 + 3 - 2 = 6\) です。これを倉庫ごとに同様に計算します。

アルゴリズム

1. 配列 \(W, L\) にそれぞれ初期荷物量と容量上限を保存する。
2. \(M\) 回の作業について、倉庫番号 \(p = P_j-1\)（0-index化）を求め、\(W[p] \mathrel{+}= C_j\) を行う。
3. 最後に全倉庫 \(i\) について \(W_i > L_i\) を満たす個数を数えて出力する。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 倉庫番号 \(P_j\) は入力では \(1\) 始まりなので、配列アクセス用に \(p = P_j - 1\) として \(0\) 始まりに直します。

• \(W_i\) や \(C_j\) は最大で \(10^9\) 規模、かつ加算が繰り返されるため、言語によっては64bit整数（Pythonなら問題なし）を使います。

• 入力サイズが大きいので、Pythonでは sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

import sys

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

    W = [0] * N
    L = [0] * N
    for i in range(N):
        W[i] = next(it)
        L[i] = next(it)

    for _ in range(M):
        p = next(it) - 1
        c = next(it)
        W[p] += c

    ans = sum(1 for i in range(N) if W[i] > L[i])
    print(ans)

if __name__ == "__main__":
    main()

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