Overview

This problem asks you to count the number of warehouses that exceed their capacity limit after performing \(M\) loading and unloading operations on \(N\) warehouses.

Analysis

Problem Organization

In this problem, the following information is given for each warehouse: - Current cargo amount \(W_i\) - Capacity limit \(L_i\)

Then, through \(M\) operations, the cargo amounts in specified warehouses increase or decrease. We need to find the number of warehouses where \(W_i > L_i\) at the end.

Key Insight

The key point of this problem is that “we don’t need to worry about intermediate states during operations.” Since we’re only asked about the state after all operations are completed, it’s sufficient to simply sum up the total change in cargo for each warehouse.

Is a Naive Approach Acceptable?

The method of simulating each operation in order: - Processing \(M\) operations: \(O(M)\) - Finally checking \(N\) warehouses: \(O(N)\)

The total is \(O(N + M)\), which runs sufficiently fast under the constraints \(N, M \leq 2 \times 10^5\).

Concrete Example

For example, suppose warehouse 1 has initial cargo amount \(W_1 = 50\) and capacity limit \(L_1 = 100\).

If the following operations are performed: - Load +30 to warehouse 1 - Unload -10 from warehouse 1 - Load +40 to warehouse 1

The final cargo amount becomes \(50 + 30 - 10 + 40 = 110\), and since \(110 > 100\), it exceeds the capacity limit.

Algorithm

1. Read input: Store each warehouse’s initial cargo amount \(W_i\) and capacity limit \(L_i\) in arrays
2. Simulate operations: For each of the \(M\) operations, add \(C_j\) to the cargo amount of target warehouse \(P_j\)
3. Count: Count the number of warehouses that satisfy \(W_i > L_i\)
4. Output: Output the count result

Complexity

• Time complexity: \(O(N + M)\)
  • Reading warehouse information: \(O(N)\)
  • Processing operations: \(O(M)\)
  • Final check: \(O(N)\)
• Space complexity: \(O(N)\)
  • Arrays to store each warehouse’s cargo amount and capacity limit

Implementation Tips

1. Handling 1-indexed: Since warehouse numbers range from \(1\) to \(N\), it’s convenient to allocate arrays with size \(N+1\) and use indices starting from \(1\).

2. Watch out for large values: \(W_i\) and \(C_j\) can be on the order of \(10^9\), and their accumulation may result in large values. In Python, you don’t need to worry about integer overflow, but in other languages, use 64-bit integer types.

3. Fast input: When \(N, M\) are large, you can speed up input processing by using sys.stdin.readline.

   Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    
    W = [0] * (N + 1)
    L = [0] * (N + 1)
    
    for i in range(1, N + 1):
        w, l = map(int, input().split())
        W[i] = w
        L[i] = l
    
    for _ in range(M):
        p, c = map(int, input().split())
        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()

---

This editorial was generated by claude4.5opus.