Overview

Each shop has a membership capacity (limit), and customers apply in order. If there is vacancy, the customer is registered. If the shop is full, we compare the applicant with the existing member who has the lowest priority and determine whether to swap them. We need to find the final number of members at each shop.

Analysis

Key Insight

For each shop, we need to be able to efficiently retrieve “the member with the lowest priority among the currently registered members” at all times.

For example, if a shop has a capacity of 2, members with priorities 3 and 7 are registered, and a customer with priority 5 applies: - The member with the lowest priority has priority 3 - The applicant’s priority 5 > 3, so the member with priority 3 is removed and the person with priority 5 is registered - Result: The shop now has members with priorities 5 and 7

Problem with the Naive Approach

If we scan all members of a shop each time to find the minimum priority, the worst case is \(O(Q \times N)\), which is too slow when \(N, Q\) are up to \(2 \times 10^5\).

Solution

Using a min-heap, we can retrieve the minimum priority and perform swaps in \(O(\log N)\). By maintaining a heap for each shop, we can process everything efficiently.

Algorithm

1. Prepare a min-heap for each shop.
2. Process the \(Q\) applications in order. For each application \((P_k, D_k)\):
   • Retrieve the applicant’s priority \(A_{P_k}\).
   • If the current number of members at shop \(D_k\) is less than the capacity \(C_{D_k}\), add the priority to the heap and increment the member count by 1.
   • If the shop is at full capacity, compare the top of the heap (minimum priority) with the applicant’s priority.
     • If the applicant’s priority is strictly greater, use heapreplace to replace the heap’s minimum value with the applicant’s priority (the member count remains unchanged).
     • Otherwise, reject the application (do nothing).
3. After processing all applications, output the number of members at each shop.

heapreplace is a function that “removes the minimum value from the heap and inserts a new value” in a single \(O(\log n)\) operation.

Complexity

• Time complexity: \(O(Q \log N)\)
  • Each application performs at most one heap operation, and the heap size is at most \(C_j \leq N\), so each operation takes \(O(\log N)\).
• Space complexity: \(O(N + M + Q)\)
  • The total number of elements stored across all shop heaps is at most \(Q\) (since each customer applies at most once). The shop array takes \(O(M)\).

Implementation Notes

• Python’s heapq module provides a min-heap, which can be used directly for the “retrieve the member with the lowest priority” operation in this problem.

• heapq.heapreplace(heap, val) is more efficient than performing pop and push separately (the heap is restructured only once).

• The member count can also be obtained via len(shops[j]), but managing it separately with a shop_sizes array avoids unnecessary overhead.

• Using sys.stdin.readline speeds up input reading. This is an important technique in competitive programming where there is a large amount of input.

  Source Code

import heapq
import sys
input = sys.stdin.readline

def main():
    N, M, Q = map(int, input().split())
    A = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    # Min-heaps for each shop (store priorities)
    shops = [[] for _ in range(M)]
    shop_sizes = [0] * M
    
    for _ in range(Q):
        P, D = map(int, input().split())
        p_priority = A[P - 1]
        d_idx = D - 1
        cap = C[d_idx]
        
        if shop_sizes[d_idx] < cap:
            heapq.heappush(shops[d_idx], p_priority)
            shop_sizes[d_idx] += 1
        else:
            # Shop is full, compare with minimum priority member
            if shops[d_idx] and p_priority > shops[d_idx][0]:
                heapq.heapreplace(shops[d_idx], p_priority)
            # else: rejected
    
    print(' '.join(str(shop_sizes[j]) for j in range(M)))

main()

This editorial was generated by claude4.6opus-thinking.