Overview

Given a collection of \(N\) types of books, process \(M\) lending requests in order, skipping any request where there aren’t enough copies available, and determine the final number of copies of each book.

Analysis

The key observations for this problem are as follows:

• Lending requests must be processed in order. Whether a request is skipped depends on the number of copies at that point in time.
• For example, if book with ID \(1\) has \(5\) copies and the requests are “lend \(3\) copies” → “lend \(3\) copies”, the first request succeeds leaving \(2\) copies, and the second request is skipped due to insufficient stock. If we ignore the order, the result would change.

A straightforward approach is to check the current stock of the relevant book for each request and subtract if there are enough copies. This is actually fast enough as-is. Processing each request only requires accessing one element of the array along with a comparison and subtraction, which takes \(O(1)\).

No special data structures or algorithms are needed — the problem can be solved by simply performing a straightforward simulation.

Algorithm

1. Read the array \(A\) of book counts (\(A[0]\) corresponds to the book with ID \(1\)).
2. Process the \(M\) lending requests from first to last:
   • If the current stock \(A[B_j - 1]\) of the book with ID \(B_j\) is at least \(C_j\), subtract \(C_j\) from \(A[B_j - 1]\).
   • Otherwise, do nothing (skip).
3. After processing all requests, output the array \(A\).

Concrete example (\(N=3\), \(A = [5, 3, 2]\)): - Request “3 copies of book ID 1” → \(A[0] = 5 \geq 3\), so update \(A[0] = 2\) - Request “3 copies of book ID 1” → \(A[0] = 2 < 3\), so skip - Request “2 copies of book ID 2” → \(A[1] = 3 \geq 2\), so update \(A[1] = 1\) - Final result: \([2, 1, 2]\)

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for initializing the array, and \(O(1)\) for each of the \(M\) requests, totaling \(O(M)\)
• Space complexity: \(O(N)\)
  • The size of the array storing the book counts

Since \(N, M \leq 10^5\), this runs sufficiently fast.

Implementation Notes

• 0-indexed vs 1-indexed conversion: Book IDs start from \(1\), but Python arrays start from \(0\), so we access them with a shift of \(1\), such as A[b - 1].

• Fast input: Since \(N, M\) can be as large as \(10^5\), using sys.stdin.buffer.read() to read all input at once and then splitting with split() is faster than calling input() repeatedly.

• Book counts and lending amounts up to \(10^9\): In Python, there’s no need to worry about integer overflow, but in C++ and similar languages, be careful about the range of int.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    for _ in range(M):
        b = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        if A[b - 1] >= c:
            A[b - 1] -= c
    print(' '.join(map(str, A)))

main()

---

This editorial was generated by claude4.6opus-thinking.