Overview

This is a simulation problem where you manage the “remaining capacity” for each counter, and for each incoming application, accept it (decrementing the capacity by one) if there is availability.

Analysis

The key point is that “applications are processed in order, and cannot be redirected to a counter other than the requested one.” In other words, when application \(j\) arrives at counter \(T_j\), all we need to do is:

• If the remaining capacity of that counter is \(> 0\), accept it (decrement the remaining capacity by 1)
• Otherwise, reject it

This simple check is sufficient.

Here, if you were to, for example, “recount how many times each counter has appeared in the past for every application,” the worst case would be \(O(M^2)\), which won’t be fast enough for \(10^5\) (causing TLE). The key insight in this problem is that you can maintain an array of remaining capacity for each counter and update it in \(O(1)\) per application.

(Concrete example) If \(C=[2,1]\) (counter 1 accepts 2 applications, counter 2 accepts 1) and applications arrive in the order \([1,2,1,2]\):

• Counter 1: remaining 2→1 (accepted)
• Counter 2: remaining 1→0 (accepted)
• Counter 1: remaining 1→0 (accepted)
• Counter 2: remaining is 0, so rejected

A total of 3 applications are accepted.

Algorithm

1. Maintain array \(C\) as the “remaining acceptance capacity for each counter.”
2. Read applications \(T_j\) sequentially from the beginning.
3. For counter \(t=T_j-1\) (converted to 0-indexed), check \(C[t]\):
   • If \(C[t] > 0\), decrement \(C[t]\) by 1 and increment the answer by 1
   • Otherwise, do nothing
4. Output the answer at the end.

Complexity

• Time complexity: \(O(N+M)\) (initialization \(N\), processing applications \(M\))
• Space complexity: \(O(N)\) (array for remaining capacity per counter)

Implementation Notes

• Since the input can be up to \(10^5\) lines, in Python it is faster to read all input at once using sys.stdin.buffer.read().

• Counter numbers \(T_j\) are 1-indexed, so convert to \(t = T_j - 1\) for array access.

• \(C_i\) can be up to \(10^9\), but since we only perform subtraction, regular integers work without any issues.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    C = [next(it) for _ in range(N)]
    ans = 0
    for _ in range(M):
        t = next(it) - 1
        if C[t] > 0:
            C[t] -= 1
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.