Overview

This is a problem where you process membership registration applications based on each customer’s priority, and determine the final number of registered members for each shop.

Analysis

In this problem, each shop has a “membership capacity,” and when a customer with a higher priority applies, there is a possibility of evicting the existing member with the lowest priority. This is a typical “efficiently manage the top \(k\) elements” type of problem, which can be efficiently handled using a priority queue (heap).

With a naive approach…

• If we manage each shop’s members with a list and perform a full search for the minimum value each time, the worst case would take \(O(Q \cdot C_{\max})\), which is too slow.
• Especially when \(C_j\) is large or \(Q\) is up to \(2 \times 10^5\), the computational complexity becomes infeasible.

Improvement

• For each shop, use a min-heap so that the minimum priority among current members can be retrieved and updated in \(O(\log C_j)\).
• Since both addition and deletion can be performed efficiently, the overall processing is sped up.
• Additionally, by also using a set for checking the existence of customer IDs, we can quickly determine whether a customer is already registered.

Algorithm

1. For each shop, prepare a min-heap to manage member information and a set to store customer IDs.
2. Process each application as follows:
   • If there is available membership capacity, simply add the customer.
   • If the membership capacity is full:
     • Compare with the top of the heap (the member with the lowest priority).
     • If the applicant’s priority is higher, remove the top element and add the new customer.
3. Finally, output the number of members for each shop (= the size of the set).

Example

For instance, if shop 1 has a membership capacity of 2, with members having priorities [10, 20], and a customer with priority 30 applies: - Remove the member with the minimum priority of 10, and add the customer with priority 30. - As a result, shop 1’s members become [20, 30].

Complexity

• Time complexity: \(O(Q \log N)\)
  • Each application triggers at most one heap operation (addition or deletion), which takes \(O(\log C_j)\), and at worst \(O(\log N)\).
• Space complexity: \(O(N + M)\)
  • Required to store information about each customer and shop.

Implementation Notes

• By inserting (priority, customer_ID) tuples into the heap, when priorities are the same, comparison automatically falls back to the customer ID. However, since all priorities are distinct in this problem, this is not a concern.

• Managing customer ID existence with a set allows for fast determination of whether a customer is already registered.

• sys.stdin.read is used to read input quickly.

  Source Code

import heapq
import sys

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(data[idx]); idx += 1
    
    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = int(data[idx]); idx += 1
    
    # 各ショップの会員リスト（優先度の最小ヒープ）
    members = [[] for _ in range(M + 1)]
    # 各ショップの会員セット（顧客IDの存在確認用）
    member_set = [set() for _ in range(M + 1)]
    
    for _ in range(Q):
        P = int(data[idx]); idx += 1
        D = int(data[idx]); idx += 1
        
        if len(member_set[D]) < C[D]:
            # 会員枠に空きがある場合
            heapq.heappush(members[D], (A[P], P))
            member_set[D].add(P)
        else:
            # 会員枠が満杯の場合
            if members[D]:
                min_priority, min_customer = members[D][0]
                if A[P] > min_priority:
                    # 最低優先度の会員を削除
                    heapq.heappop(members[D])
                    member_set[D].discard(min_customer)
                    # 新しい会員を追加
                    heapq.heappush(members[D], (A[P], P))
                    member_set[D].add(P)
            # それ以外は却下
    
    result = []
    for j in range(1, M + 1):
        result.append(str(len(member_set[j])))
    
    print(' '.join(result))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.