Overview

This problem requires processing \(Q\) membership applications in order across \(M\) shops, and determining the final number of members at each shop. When a shop’s membership slots are full, you need to efficiently simulate the rule of swapping the applicant with the member who has the lowest priority.

Analysis

The key to this problem is: when an application arrives for a shop whose membership slots are full, how quickly can we find the member with the lowest priority currently in that shop and perform the swap?

Naive Approach

Suppose we maintain each shop’s member list in an array and sort the list to find the minimum value each time an application arrives. - Processing per application: \(O(K \log K)\) for \(K\) members - Overall complexity: \(O(Q \times N \log N)\)

Since \(N, Q\) can be up to \(2 \times 10^5\), this approach will not meet the time limit.

Efficient Approach

We need a data structure that can efficiently perform “retrieve the minimum” and “add/remove elements.” The ideal choice for this is a priority queue (heap). By managing each shop’s state with a Min-Heap, the following operations can be performed efficiently: - Checking the member with the lowest priority: \(O(1)\) - Adding/swapping a member: \(O(\log (\text{number of members}))\)

Since each customer applies only once, the total number of elements stored across all heaps is at most \(Q\), which is sufficiently fast to process.

Algorithm

1. Prepare an empty min-heap shops_heaps[j] for each shop \(j\).
2. Process the \(Q\) applications in order. For each application \((P_k, D_k)\):
   • If the current number of members (heap size) of shop \(D_k\) is less than the membership capacity \(C_{D_k}\):
     • Add the priority \(A_{P_k}\) of customer \(P_k\) to the heap.
   • If the membership slots are full:
     • Compare the top element (minimum value) of the heap with \(A_{P_k}\).
     • If \(A_{P_k}\) is larger, remove the minimum value from the heap and add \(A_{P_k}\).
     • Otherwise, do nothing (application rejected).
3. After all processing is complete, output the size of each heap.

Complexity

• Time complexity: \(O(Q \log N)\)
  • For each of the \(Q\) applications, heap operations (add/swap) are performed in \(O(\log C_j)\). Since \(C_j \leq N\), the overall complexity is \(O(Q \log N)\).
• Space complexity: \(O(N + M + Q)\)
  • We store priorities \(A\), membership capacities \(C\), and a total of at most \(Q\) elements across all shop heaps, so memory usage is on the order of linear.

Implementation Notes

• Fast I/O: Since \(N, M, Q\) can be large, in Python it is common to speed up I/O using sys.stdin.read().split() and sys.stdout.write.

• heapq.heapreplace: When swapping members, using heapreplace is more efficient than calling heappop followed by heappush. This function performs the extraction of the minimum and insertion of a new element in a single operation.

• Converting to 0-indexed: The customer numbers and shop numbers in the input are 1-indexed (starting from 1), so when using them as list indices, you need to subtract 1 to convert to 0-indexed.

  Source Code

import sys
import heapq

def solve():
    # 高速な入力読み込み: すべての入力を一度に読み込み、整数のリストに変換します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(map(int, input_data))
    
    try:
        N = next(it)
        M = next(it)
        Q = next(it)
    except StopIteration:
        return
    
    # A[i] は顧客 i+1 の優先度を格納します
    A = [next(it) for _ in range(N)]
        
    # C[j] はショップ j+1 の会員枠を格納します
    C = [next(it) for _ in range(M)]
        
    # 各ショップの現在の会員の優先度を最小ヒープで管理します
    # これにより、最も優先度が低い会員を O(log(会員枠)) で取得・更新できます
    shops_heaps = [[] for _ in range(M)]
    
    # Q 件の申請を順番に処理します
    for _ in range(Q):
        try:
            p_val = next(it)
            d_val = next(it)
        except StopIteration:
            break
            
        # 1-indexed から 0-indexed に変換
        p_idx = p_val - 1
        d_idx = d_val - 1
        
        priority = A[p_idx]
        capacity = C[d_idx]
        heap = shops_heaps[d_idx]
        
        if len(heap) < capacity:
            # 会員枠に空きがある場合は、そのまま登録されます
            heapq.heappush(heap, priority)
        elif priority > heap[0]:
            # 会員枠が満杯の場合、最も優先度が低い会員（heap[0]）と比較します
            # 申請者の優先度が真に大きければ、入れ替えを行います
            heapq.heapreplace(heap, priority)
        # それ以外の場合、申請は却下されます
            
    # 各ショップの最終的な会員数を取得します
    ans = [len(h) for h in shops_heaps]
    
    # 結果をスペース区切りで出力します
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == '__main__':
    solve()

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