Overview

This problem requires processing each application in order, where for each shop we “add if there’s room, or compare with the minimum-priority member and swap if the shop is full,” then determine the final number of members.

Analysis

When viewed per shop, this rule is equivalent to performing the operation “keep only the top \(C_j\) members by priority among those currently registered” online in the order of applications.

Why a Naive Approach Is Too Slow

When shop \(d\) is full, we need to find the “member with the lowest priority.”

• If we store members in an array and search for the minimum each time, a single application can cost \(O(C_d)\)
  → In the worst case with \(Q=2\times10^5\) and large \(C_d\), this approaches \(O(NQ)\) and results in TLE.
• Even if we maintain a sorted structure, we need to carefully manage the cost of insertion and deletion.

Solution Approach

When the shop is full, all we need is the “current minimum priority.”
Therefore, if we maintain a data structure that can efficiently extract the minimum (min-heap) for each shop, we can achieve:

• Retrieving the minimum priority: \(O(1)\) (heap top)
• Addition/swap: \(O(\log C_d)\)

Additionally, in this problem: - The same customer never applies more than once - All customer priorities are distinct

So we don’t need to worry about scenarios like “a customer who was once rejected comes back through another application,” and each shop can be processed independently.

Algorithm

For each shop \(j\), prepare a min-heap heaps[j] with elements of the form (priority, customer ID), where the heap top is the member with the lowest priority in that shop.

When processing application \((p, d)\):

1. Let \(a = A_p\) be the applicant’s priority.
2. If len(heaps[d]) < C_d (there is still room):
   • Register directly with heappush(heaps[d], (a, p)).
3. Otherwise, if the shop is full, the heap top (amin, *) is the “member with the lowest priority,” so:
   • If \(amin < a\), swap them:
     heapreplace(heaps[d], (a, p)) (remove the minimum element and insert the new element)
   • Otherwise (if \(a\) is smaller or equal), reject (do nothing)

Finally, for each shop \(j\), len(heaps[j]) is the final number of members.

(Example) For a shop with capacity 2 and current priorities {10, 30} (minimum is 10): if priority 20 arrives, swap with 10 to get {20, 30}; if priority 5 arrives, reject. The heap efficiently realizes this behavior.

Complexity

• Time complexity: \(O\!\left(\sum_{k=1}^{Q} \log C_{D_k}\right) \subseteq O(Q\log N)\)
  (at most one heap operation per application)
• Space complexity: \(O(N + M)\)
  (the total number of elements in heaps is at most the number of accepted people, which is \(O(N)\), and the shop array is \(O(M)\))

Implementation Notes

• We store (priority, customer ID) in the heap, but only the priority is essential for comparison (since all priorities are distinct, the customer ID isn’t strictly necessary, but using tuples makes handling easier).

• For the “remove and add” operation when the shop is full, heappop + heappush also works, but using heapreplace allows it to be written in one call with a smaller constant factor.

• Since the input size is up to \(2\times10^5\), reading all at once with sys.stdin.buffer.read() and processing as a sequence of integers is faster.

• Since we only need the number of members in each shop at the end, there is no need to extract and sort the heap contents.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it); M = next(it); Q = next(it)

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = next(it)

    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = next(it)

    heaps = [[] for _ in range(M + 1)]

    for _ in range(Q):
        p = next(it); d = next(it)
        h = heaps[d]
        ap = A[p]
        if len(h) < C[d]:
            heapq.heappush(h, (ap, p))
        else:
            if h[0][0] < ap:
                heapq.heapreplace(h, (ap, p))

    out = [str(len(heaps[j])) for j in range(1, M + 1)]
    sys.stdout.write(" ".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.