概要

\(N\) 個の倉庫があり、それぞれに現在の荷物量と容量上限が与えられます。その後、\(M\) 回の搬入・搬出操作が行われるため、最終的にどれだけの倉庫が容量オーバーになるかを求める問題です。

考察

この問題は、単純にシミュレーションを行えば解けますが、制約が非常に大きい（\(N, M \leq 2 \times 10^5\)）ため、効率的な処理が必要です。

重要な観察

• 各操作は「特定の倉庫の荷物量を増減させる」だけなので、差分更新で処理できます。
• 最終的な結果はすべての操作が終わったあとに判定すれば良いので、途中でオーバーになったかは気にしなくてよいです。

素朴なアプローチの問題点

もし入出力を1行ずつ input() で受け取ると、Python では非常に遅く、TLE してしまう可能性があります。特に \(M\) が最大 \(2 \times 10^5\) あるため、高速な入力方法を使う必要があります。

解決策

• 入力を一度に読み込み（sys.stdin.read）、トークンごとに分割して処理することで、高速化を図ります。
• 荷物量の更新は配列 W を使い、各操作で該当する倉庫の値を直接加算します。

アルゴリズム

1. 入力をすべて一括で読み込む。
2. 倉庫の初期状態（現在の荷物量 \(W_i\) と上限 \(L_i\)）をリストに保存。
3. \(M\) 回の操作について、指定された倉庫の荷物量を更新（加算）。
4. 全ての操作が終わったら、各倉庫について最終的な荷物量が上限を超えるか判定し、カウントする。

計算量

• 時間計算量: \(O(N + M)\)
  （入力処理と操作適用、そして最後のチェックが線形時間で可能）
• 空間計算量: \(O(N)\)
  （倉庫の情報を保持する配列）

実装のポイント

• 配列のインデックスを1-originとして扱うために、W[0] などは使わず W[1] から使うようにしている。
• 入力を高速に行うために sys.stdin.read を使用している。
• 各操作は定数時間で処理できるため、ループ内で逐次更新すれば十分高速である。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    W = [0] * (N + 1)
    L = [0] * (N + 1)
    
    for i in range(1, N + 1):
        W[i] = int(data[idx])
        idx += 1
        L[i] = int(data[idx])
        idx += 1
    
    for _ in range(M):
        P = int(data[idx])
        idx += 1
        C = int(data[idx])
        idx += 1
        W[P] += C
    
    count = 0
    for i in range(1, N + 1):
        if W[i] > L[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。