Overview

This problem involves managing the inventory of books by genre across multiple libraries, processing loan requests given in chronological order, and determining the final inventory and the number of failed loan attempts.

Analysis

First, the problem input can contain very large values (for example, \(Q\) can be up to \(2 \times 10^5\)), so efficient input/output processing is necessary. Since Python’s standard input() function is slow, we use sys.stdin.read to speed things up.

We manage the number of books per genre for each library using a two-dimensional list or similar structure, and for each loan request, we check whether the specified library has stock of the specified genre. If stock is available, we decrease it; otherwise, we simply increment the failure count.

Although this problem can be solved with a straightforward approach, neglecting efficient input processing will result in TLE (Time Limit Exceeded). Additionally, since the indices are given in 1-origin, they need to be adjusted to 0-origin.

Algorithm

1. First, read the initial inventory for all libraries and genres.
2. For each loan request, repeat the following:
   • Check the inventory of genre \(d_k\) at the specified library \(v_k\).
   • If the inventory is 1 or more, decrease the inventory by 1.
   • If the inventory is 0, increment the failure count by 1.
3. After processing all requests, output the final inventory of each library and the number of failures.

Complexity

• Time complexity: \(O\left(\sum_{i=1}^{N} M_i + Q\right)\) (Total of reading the initial inventory and processing the loan requests)
• Space complexity: \(O\left(\sum_{i=1}^{N} M_i\right)\) (For storing the inventory per genre for each library)

Implementation Notes

• Use sys.stdin.read for fast input processing.

• Since library and genre numbers are 1-indexed, they need to be converted to 0-indexed internally (by subtracting 1).

• Loan request processing is done with simple conditional branching, taking care not to let the inventory go below 0.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    
    libraries = []
    for i in range(N):
        M = int(data[idx])
        idx += 1
        books = list(map(int, data[idx:idx+M]))
        idx += M
        libraries.append(books)
    
    Q = int(data[idx])
    idx += 1
    
    fail_count = 0
    for _ in range(Q):
        v = int(data[idx]) - 1
        d = int(data[idx+1]) - 1
        idx += 2
        if libraries[v][d] > 0:
            libraries[v][d] -= 1
        else:
            fail_count += 1
    
    for lib in libraries:
        print(' '.join(map(str, lib)))
    print(fail_count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.