Overview

This problem involves managing the inventory of each library and each genre using arrays, processing loan requests one by one in chronological order, and reducing inventory (or incrementing the failure count if it’s 0).

Analysis

The key insight is that each request only references the inventory of “a specific genre \(d_k\) at a specific library \(v_k\)”, and no information about other genres or other libraries is needed. In other words, for each request, we only need to do one of the following two things:

• If the inventory is \(>0\), subtract \(1\)
• If it’s \(=0\), increment the failure count by \(1\)

Common pitfalls when implementing this naively include:

• Searching through the input for library information each time a request is made / overusing dictionary lookups
• Reading as strings and parsing each time
• Calling print excessively for each output

Since this problem has \(\sum M_i \le 10^5\) and the number of requests \(Q \le 2\times 10^5\), which are large values, we need to maintain the data in a form that allows “\(O(1)\) updates per request” and also use fast I/O.

To achieve this, we store each library’s inventory directly as a 2D array (list of lists), and when a request \((v,d)\) comes in, we directly update libs[v][d]. This allows each request to be processed in constant time.

Example: If the inventory of genre 3 at library 2 is 0, attempting to borrow will not reduce it, and only the failure count increases.

Algorithm

1. Read \(N\) from input.
2. For each library \(i\), read the number of genres \(M_i\) and the initial inventory \(S_{i,1..M_i}\), and store them as libs[i] = [S_{i,1}, ..., S_{i,M_i}].
3. Process the \(Q\) requests in order:
   • Convert v, d to 0-indexed (v-1, d-1)
   • If libs[v][d] > 0, then libs[v][d] -= 1
   • Otherwise, fail += 1
4. Finally, output each library’s array as space-separated values, and output fail on the last line.

Complexity

• Time complexity: \(O\!\left(\sum_{i=1}^{N} M_i + Q\right)\) (Reading initial inventory + processing each request once)
• Space complexity: \(O\!\left(\sum_{i=1}^{N} M_i\right)\) (Storing inventory for all genres)

Implementation Tips

• Convert to 0-indexed: Since the input is 1-indexed, convert to v-1, d-1 to simplify array access.

• Fast input: Using sys.stdin.buffer.read().split() to read everything at once and extracting values sequentially with iter is fast enough even in Python.

• Fast output: Instead of calling print many times, accumulate strings in an array out and output them all at once with "\n".join(out) at the end.

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    libs = []
    for _ in range(N):
        Mi = next(it)
        libs.append([next(it) for _ in range(Mi)])

    Q = next(it)
    fail = 0
    for _ in range(Q):
        v = next(it) - 1
        d = next(it) - 1
        a = libs[v]
        if a[d] > 0:
            a[d] -= 1
        else:
            fail += 1

    out = []
    for a in libs:
        out.append(" ".join(map(str, a)))
    out.append(str(fail))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.