Overview

Given \(N\) warehouses, we perform \(M\) loading/unloading operations, and we need to find the number of warehouses where the “current load \(W_i\)” strictly exceeds the “capacity limit \(L_i\)” after all operations are completed.

Analysis

The key point of this problem is that “we only need to check the final state after all operations are completed.”

Even if a warehouse temporarily exceeds its capacity during the operations, it is not counted if items are later removed to bring it back within the limit. Conversely, even if it starts within the limit, it is counted if it ultimately exceeds the limit.

Efficient Processing

Looking at the constraints, \(N\) and \(M\) can be as large as \(2 \times 10^5\), so efficient processing is necessary. 1. Data Storage: Manage each warehouse’s “current load” and “capacity limit” using arrays (lists in Python). 2. Update Operations: For each operation \(j\), simply add \(C_j\) to the load of the specified warehouse \(P_j\). This takes \(O(1)\) per operation. 3. Final Check: After all operations are complete, check each of the \(N\) warehouses one by one. This takes \(O(N)\).

If we checked the state of all warehouses after every operation, it would take \(O(N \times M)\) time, which with the given constraints (approximately \(4 \times 10^{10}\) total computations) would not finish within the time limit. With our simulation approach, the total complexity is \(O(N + M)\), which is well within the time limit.

Algorithm

1. Prepare an array to store the initial loads \(W\) and an array to store the capacity limits \(L\) for the warehouses.
2. For each of the \(M\) operations, repeat the following:
   • Convert the warehouse number \(P_j\) to a 0-based index (\(P_j - 1\)).
   • Add \(C_j\) to \(W[P_j - 1]\).
3. Initialize a counter to \(0\), and for each warehouse \(i\) (from \(0\) to \(N-1\)), check the following:
   • If \(W[i] > L[i]\), increment the counter by \(1\).
4. Output the final value of the counter.

Complexity

• Time Complexity: \(O(N + M)\)
  • Reading the data takes \(O(N)\), simulating the operations takes \(O(M)\), and the final check takes \(O(N)\). Since \(N, M \leq 2 \times 10^5\), the total number of operations is approximately \(4 \times 10^5\), which runs efficiently.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the arrays storing each warehouse’s load and capacity limit.

Implementation Notes

• Fast I/O: In Python, when \(N, M\) exceed \(10^5\), repeatedly calling input() can become a bottleneck due to slow input. By reading all input at once using sys.stdin.read().split(), execution time can be significantly reduced.

• Converting from 1-indexed to 0-indexed: The problem gives warehouse numbers from \(1\) to \(N\), but arrays in programs typically start from \(0\), so we need to subtract \(1\) from the number when accessing the array.

• Comparison Operator: The condition “exceeds the capacity limit” means “greater than the limit,” so we use > instead of >=.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペース、改行、タブ）で分割してトークンのリストを作成します。
    # N, M が最大 2*10^5 であるため、この方法は Python において非常に高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # トークンを整数に変換するイテレータを作成します。
    # map は Python 3 ではイテレータを返すため、メモリ効率が良いです。
    it = map(int, input_data)
    
    # 倉庫の数 N と作業の回数 M を読み込みます。
    try:
        N = next(it)
        M = next(it)
    except StopIteration:
        return
    
    # 各倉庫の現在の荷物量 W と容量上限 L を格納するリストを初期化します。
    weights = [0] * N
    limits = [0] * N
    
    # 各倉庫の初期情報を読み込みます。
    for i in range(N):
        weights[i] = next(it)
        limits[i] = next(it)
        
    # M 回の荷物の搬入・搬出作業を処理します。
    for _ in range(M):
        p = next(it) - 1  # 倉庫番号は 1-indexed なので 0-indexed に変換します。
        c = next(it)
        weights[p] += c
        
    # すべての作業終了後に容量上限 L を超えている倉庫の個数をカウントします。
    # 「超える」は厳密に大きい（weights[i] > limits[i]）ことを指します。
    ans = 0
    for i in range(N):
        if weights[i] > limits[i]:
            ans += 1
            
    # 結果を出力します。
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.