Overview

There are \(N\) counters, each with a predetermined maximum number of requests it can process. This is a simulation problem where you examine \(M\) incoming requests in order, determine whether the specified counter has remaining capacity, and find the total number of accepted requests.

Analysis

The key points for solving this problem are the following three:

1. Process requests in order: Since requests are processed in the order they arrive, we need to simulate them in the order they are received as input.
2. Manage the state of each counter: By managing the remaining processing capacity of each counter using an array (list), we can immediately determine whether a specific counter has availability.
3. Efficient processing: The number of counters \(N\) and the number of requests \(M\) are at most \(10^5\). If we can perform the operation “check and update a counter’s availability” in \(O(1)\) for each request, the overall time complexity becomes \(O(N + M)\), which is well within the time limit.

Note that counter numbers are given from \(1\) to \(N\), but since arrays (lists) in programs typically start from \(0\), we need to handle the index as \(T_j - 1\).

Algorithm

The program is implemented with the following steps:

1. Read the number of counters \(N\), the number of requests \(M\), and the capacity of each counter \(C_1, \ldots, C_N\) as input.
2. Prepare an array C to manage the remaining capacity of each counter.
3. Read the \(M\) requests \(T_j\) in order and perform the following operations:
   • Check whether the remaining capacity of counter \(T_j\) (index \(T_j - 1\) in the array) is at least \(1\).
   • If it is at least \(1\), decrease that counter’s capacity by \(1\) and increment the accepted request count.
   • If the capacity is \(0\), ignore that request and move on to the next one.
4. Output the final count.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\) and processing requests (the loop) takes \(O(M)\), so the entire process runs in linear time.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array that stores the capacity of each counter.

Implementation Notes

• Fast I/O: When handling input on the scale of \(10^5\) in Python, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), which can reduce execution time.

• Index conversion: Don’t forget to always subtract \(1\) to convert the counter numbers in the problem statement (1-indexed) to array indices (0-indexed).

• Handling large numbers: The capacity \(C_i\) of each counter can be as large as \(10^9\), which is very large, but since Python’s integer type automatically handles arbitrary-precision integers, there is no need to worry about overflow.

  Source Code

import sys

def solve():
    # 全ての入力を読み込み、空白（スペースや改行）で分割してリスト化する
    # この手法は競技プログラミングにおいて、大量の入力を高速に処理するのに適している
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 窓口の数 N と 申請の数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各窓口の処理可能件数 C をリストとして取得（0-indexedにするため、アクセス時は T_j - 1 とする）
    # C は input_data のインデックス 2 から 2 + N - 1 まで
    C = list(map(int, input_data[2:2+N]))
    
    # 受付が成立した総件数をカウントする変数
    accepted_count = 0
    
    # 各申請を順番に処理する
    # 申請 T_j は input_data のインデックス 2 + N から 2 + N + M - 1 まで
    for i in range(M):
        # 希望する窓口番号（1-indexed）を整数に変換
        t_j = int(input_data[2 + N + i])
        
        # 窓口のインデックスを 0-indexed に変換
        idx = t_j - 1
        
        # 希望する窓口に空きがあるか確認
        if C[idx] > 0:
            # 空きがあれば受付を成立させ、残り処理可能件数を1減らす
            C[idx] -= 1
            accepted_count += 1
            
    # 結果を出力
    print(accepted_count)

if __name__ == '__main__':
    solve()

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