Overview

This problem asks you to process loan requests \((B_j, C_j)\) in order while maintaining the inventory \(A_i\) for each book, reducing the inventory only when there is sufficient stock, and outputting the final inventory.

Analysis

The key point is that “requests are processed in order, and requests that cannot be fulfilled due to insufficient inventory are skipped without changing the inventory.” In other words, each request’s approval depends on the inventory at that point in time, which also affects subsequent requests.

What we need to do is very straightforward — for each request:

• If the current inventory of book \(B_j\) is at least \(C_j\), then \(A_{B_j} \leftarrow A_{B_j} - C_j\)
• Otherwise, do nothing

and simply repeat this process.

The constraints are \(N, M \le 10^5\), so an \(O(M)\) simulation that processes requests one by one is more than sufficient. On the other hand, if the implementation takes \(O(N)\) per request — for example, by searching through all books each time or using unnecessarily complex data structures for updates — it becomes \(O(NM)\), which can reach up to \(10^{10}\) operations and result in TLE.

(Concrete example) Inventory \(A=[3,1]\), with requests: 1. \((1,2)\) → Inventory is 3, so execute: \(A=[1,1]\) 2. \((1,2)\) → Inventory is only 1, so skip: \(A=[1,1]\) 3. \((2,1)\) → Execute: \(A=[1,0]\)

As shown, we simply repeat “check if there’s enough → subtract” in order.

Algorithm

1. Read the array \(A\) (it’s convenient to manage with 0-indexing).
2. Process each request \((B, C)\) in input order.
   • Convert to 0-index by setting \(b = B - 1\)
   • If \(A[b] \ge C\), then \(A[b] \mathrel{-}= C\) (reduce inventory)
   • Otherwise, do nothing
3. Finally, output the array \(A\).

Complexity

• Time complexity: \(O(N + M)\) (reading the initial inventory \(O(N)\) and processing requests \(O(M)\))
• Space complexity: \(O(N)\) (only the inventory array \(A\))

Implementation Tips

• Since the input can be up to \(2\times 10^5\) lines, in Python it is safer to use fast input methods like sys.stdin.buffer.read().

• Book numbers \(B_j\) are 1-indexed, so subtract \(1\) to convert to 0-index for array access.

• For output, using " ".join(...) to print everything in a single line is faster.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    for _ in range(M):
        b = int(next(it)) - 1
        c = int(next(it))
        if A[b] >= c:
            A[b] -= c
    sys.stdout.write(" ".join(map(str, A)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.