Overview

This is a simulation problem where you manage the book inventory by genre across \(N\) libraries, process \(Q\) lending requests in chronological order, and determine the final inventory counts and the total number of failed lending attempts.

Analysis

The operations required in this problem are very simple: for each lending request, “reduce the stock by 1 if available” or “count it as a failure if out of stock.”

• Feasibility of simulation: The number of lending requests is at most \(2 \times 10^5\), and the total number of genres across all libraries is at most \(10^5\). For each request, checking and updating the stock of a specific genre at a specific library can be done in \(O(1)\), so the overall computation can be processed in \(O(\sum M_i + Q)\) time. This is well within the time limit.
• Choice of data structure: Since we need to access inventory counts using two indices — “library number” and “genre number” — it is natural to manage them with a 2-dimensional array (a list of lists in Python).
• Speeding up I/O: Since the input data can contain up to several hundred thousand items, repeatedly calling input() may result in slow execution. Using techniques like sys.stdin.read().split() to read all input at once is effective.

Algorithm

1. Reading input: Read all input at once as a list of numbers.
2. Initializing inventory data:
   • Read each library’s information sequentially and create a 2-dimensional list where libraries[i][j] represents “the number of books of genre \(j\) at library \(i\).”
   • Since the library numbers and genre numbers in the problem statement start from 1 (1-indexed), adjust them to match the program’s 0-indexed array indices.
3. Processing lending requests:
   • Process the \(Q\) requests sequentially.
   • If library \(v_k\) has at least 1 book of genre \(d_k\) in stock, reduce the stock by 1.
   • If the stock is 0, increment the failure count (failed_count) by 1.
4. Outputting results:
   • Output the final inventory of each library, separated by spaces.
   • Finally, output the accumulated failure count.

Complexity

• Time complexity: \(O(\sum M_i + Q)\)
  • Reading input takes \(O(\sum M_i + Q)\), processing lending requests takes \(O(Q)\), and outputting results takes \(O(\sum M_i)\).
• Space complexity: \(O(\sum M_i + Q)\)
  • \(O(\sum M_i)\) memory is used to store the inventory for all genres, and \(O(\sum M_i + Q)\) memory is used to store the input data.

Implementation Notes

• 1-indexed vs 0-indexed: The input values \(v_k\) and \(d_k\) start from 1. When using them as array indices, you must subtract 1.
• Fast output in Python: Instead of calling print multiple times, you can accumulate the strings to output in a list, join them with "\n".join(), and output everything at once to reduce execution time.
• Memory management: sys.stdin.read().split() loads all data into memory, so care is needed for extremely large inputs. However, with the constraints of this problem (approximately \(3 \times 10^5\) integers in total), there is no issue.

import sys

def solve():
    # Read all data from standard input, split by whitespace into a list
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    tokens = list(map(int, input_data))
    
    ptr = 0
    # Get the number of libraries N
    N = tokens[ptr]
    ptr += 1
    
    # List to store the number of books per genre for each library
    libraries = [None] * N
    for i in range(N):
        m_i = tokens[ptr]
        ptr += 1
        # Use slicing to get the initial inventory for each genre of library i
        libraries[i] = tokens[ptr : ptr + m_i]
        ptr += m_i
        
    # Get the number of lending requests Q
    if ptr >= len(tokens):
        Q = 0
    else:
        Q = tokens[ptr]
        ptr += 1
    
    failed_count = 0
    # Process each lending request sequentially
    for _ in range(Q):
        v_k = tokens[ptr]
        d_k = tokens[ptr + 1]
        ptr += 2
        
        # Convert to 0-indexed
        lib_idx = v_k - 1
        genre_idx = d_k - 1
        
        # Check and update inventory
        if libraries[lib_idx][genre_idx] > 0:
            libraries[lib_idx][genre_idx] -= 1
        else:
            failed_count += 1
            
    # Build output results
    output_results = []
    for i in range(N):
        output_results.append(" ".join(map(str, libraries[i])))
    output_results.append(str(failed_count))
    
    # Output all at once
    sys.stdout.write("\n".join(output_results) + "\n")

if __name__ == '__main__':
    solve()

Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    # sys.stdin.read().split() は、スペース、タブ、改行などのすべての空白文字を処理します。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    # 入力が空の場合は何もしない
    if not input_data:
        return
    
    # リストの全要素を整数に変換する
    # map(int, ...) は高速に変換を行うことができます。
    tokens = list(map(int, input_data))
    
    ptr = 0
    # 図書館の数 N を取得
    if ptr >= len(tokens):
        return
    N = tokens[ptr]
    ptr += 1
    
    # 各図書館のジャンルごとの蔵書数を格納するリスト
    # libraries[i] は図書館 (i+1) の各ジャンルの蔵書数のリストを保持します。
    libraries = [None] * N
    for i in range(N):
        # 図書館 i のジャンル数 M_i を取得
        m_i = tokens[ptr]
        ptr += 1
        # スライスを使用して、図書館 i の各ジャンルの初期蔵書数を取得する
        # スライスによって新しいリストが作成されるため、元の tokens は変更されず、
        # libraries[i] の値を個別に更新することができます。
        libraries[i] = tokens[ptr : ptr + m_i]
        ptr += m_i
        
    # 貸出申請の件数 Q を取得
    if ptr >= len(tokens):
        Q = 0
    else:
        Q = tokens[ptr]
        ptr += 1
    
    failed_count = 0
    # 各貸出申請を順に処理する
    for _ in range(Q):
        if ptr + 1 >= len(tokens):
            break
        v_k = tokens[ptr]
        d_k = tokens[ptr + 1]
        ptr += 2
        
        # 図書館番号 v_k とジャンル番号 d_k は 1-indexed なので、
        # リストのインデックスに合わせて 0-indexed に変換する
        lib_idx = v_k - 1
        genre_idx = d_k - 1
        
        # 在庫があるか確認し、あれば 1 冊減らし、なければ失敗回数をカウントする
        if libraries[lib_idx][genre_idx] > 0:
            libraries[lib_idx][genre_idx] -= 1
        else:
            failed_count += 1
            
    # 出力結果のリストを準備する
    output_results = []
    for i in range(N):
        # 各図書館の残り蔵書数をスペース区切りで連結
        output_results.append(" ".join(map(str, libraries[i])))
    
    # 貸出が失敗した合計回数を追加
    output_results.append(str(failed_count))
    
    # すべての結果を改行で連結して一括出力する
    sys.stdout.write("\n".join(output_results) + "\n")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.