Overview

The final amount of cargo in each warehouse is “the initial amount \(W_i\) plus the total of all increases and decreases applied to that warehouse,” so we count the number of warehouses where \(W_i > L_i\) after all operations are completed.

Analysis

The key observation is that we only need to know the “final state after all operations are completed,” not the “intermediate states.”
Operation \(j\) simply adds \(C_j\) to the cargo amount of warehouse \(P_j\) (subtracts if negative), so we can determine the final amount by accumulating the changes for each warehouse.

A naive approach of “re-examining all warehouses each time and recounting the number of overflowing ones” would cost \(O(N)\) per operation, resulting in a total of \(O(NM)\), which could be as large as \(4 \times 10^{10}\) and would result in TLE.
However, in this problem, each operation only changes “one target warehouse,” so it is sufficient to add to that warehouse’s value and check all warehouses just once at the end.

(Example) If warehouse 1 has an initial value of \(W_1=5\) and receives operations \(+3, -2\), the final value is \(5 + 3 - 2 = 6\). We perform the same calculation for each warehouse.

Algorithm

1. Store the initial cargo amounts and capacity limits in arrays \(W\) and \(L\), respectively.
2. For each of the \(M\) operations, determine the warehouse index \(p = P_j-1\) (converting to 0-indexed), and perform \(W[p] \mathrel{+}= C_j\).
3. Finally, count and output the number of warehouses \(i\) satisfying \(W_i > L_i\).

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Warehouse numbers \(P_j\) are 1-indexed in the input, so convert to 0-indexed as \(p = P_j - 1\) for array access.

• Since \(W_i\) and \(C_j\) can be up to \(10^9\) in magnitude and additions are repeated, use 64-bit integers depending on the language (not an issue in Python).

• Since the input size is large, in Python it is faster to read all input at once using sys.stdin.buffer.read().

  Source Code

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

This editorial was generated by gpt-5.2-high.