Overview

This problem requires simulating a system where multiple customers apply for membership registration at shops. The system dynamically registers and unregisters members based on each shop’s membership capacity and customer priority, and we need to determine the final number of members at each shop.

Analysis

The core of the problem is efficiently managing the member with the lowest priority among the currently registered members at each shop. Every time an application arrives, if the shop’s current membership count has reached its capacity, we need to compare the priority of the minimum-priority member with the applicant’s priority.

A naive approach would be to maintain each shop’s member list as an array and search for the minimum priority linearly each time. However, this would require examining up to N members for each of Q applications, resulting in a worst-case time complexity of O(QN), which is too slow given the constraints (N, Q ≤ 2×10^5).

Therefore, we use a min-heap (priority queue) as a data structure that can efficiently retrieve the minimum priority at each shop. However, elements removed from the heap need to be processed lazily.

Algorithm

1. Data Structure Preparation:

   • shop_members[j]: A set of customer IDs currently registered at shop j (for existence checks)
   • shop_heap[j]: A min-heap storing members of shop j as (priority, customer ID)
   • customer_shop[i]: The shop ID where customer i is currently registered (0 means unregistered)

2. Application Processing:

   • If the customer is already registered at another shop, remove them from the original shop (remove from the set; use lazy deletion for the heap)
   • If the destination shop’s membership count is below capacity:
     • Register the customer as a new member (add to both the set and the heap)
   • If the capacity is full:
     • Pop from the top of the heap until a valid member (one that exists in the set) is found (lazy deletion)
     • Compare the valid minimum-priority member with the applicant:

          - If the applicant's priority is higher: Remove the minimum-priority member and register the applicant
          - Otherwise: Reject the application
       

3. Result Output:

   • After all processing, output the size of shop_members for each shop

Complexity

• Time complexity: \(O(Q \log N)\)
  • Each application involves a constant number of heap operations (push/pop), each costing \(O(\log N)\)
  • The additional cost due to lazy deletion is amortized constant time
• Space complexity: \(O(N + M)\)
  • Each data structure holds information for at most N customers and M shops

Implementation Notes

• Lazy Deletion Handling: Instead of directly removing elements from the heap, we manage whether elements are valid using the shop_members set, and skip invalid elements during heap operations

• Maintaining State Consistency: The three structures — customer’s shop membership information (customer_shop), shop member sets (shop_members), and heaps (shop_heap) — must always be kept in sync

• Efficiency: Existence checks using sets run in \(O(1)\), and heap operations run in \(O(\log N)\), enabling efficient overall processing

  Source Code

import sys
import heapq

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it)); Q = int(next(it))
    A = [0] * (N+1)
    for i in range(1, N+1):
        A[i] = int(next(it))
    
    C = [0] * (M+1)
    for j in range(1, M+1):
        C[j] = int(next(it))
    
    # 各ショップの現在の会員を管理: 最小ヒープ（優先度が低い順）と、会員の集合（所属ショップを追跡するため）
    shop_members = [set() for _ in range(M+1)]
    shop_heap = [[] for _ in range(M+1)]  # 最小ヒープ（優先度、顧客ID）を格納
    
    # 各顧客が現在所属しているショップ（0は未所属）
    customer_shop = [0] * (N+1)
    
    for _ in range(Q):
        p = int(next(it)); d = int(next(it))
        current_shop = customer_shop[p]
        if current_shop == d:
            continue
            
        # 現在のショップから削除（もし所属していれば）
        if current_shop != 0:
            shop_members[current_shop].discard(p)
            # ヒープからは削除できないので、遅延削除を行う
        
        # 新しいショップに登録を試みる
        target_shop = d
        if len(shop_members[target_shop]) < C[target_shop]:
            # 空きがあるので登録
            customer_shop[p] = target_shop
            shop_members[target_shop].add(p)
            heapq.heappush(shop_heap[target_shop], (A[p], p))
        else:
            # 空きがないので、最小優先度と比較
            while shop_heap[target_shop]:
                min_priority, min_customer = shop_heap[target_shop][0]
                if min_customer not in shop_members[target_shop]:
                    # 遅延削除：ヒープの先頭が実際には存在しない会員ならpop
                    heapq.heappop(shop_heap[target_shop])
                    continue
                break
            else:
                # ヒープが空（実際には会員枠いっぱいだがヒープに有効な要素がない）ということはないはず
                continue
                
            if A[p] > min_priority:
                # 入れ替え
                removed_customer = min_customer
                heapq.heappop(shop_heap[target_shop])
                shop_members[target_shop].remove(removed_customer)
                customer_shop[removed_customer] = 0
                
                customer_shop[p] = target_shop
                shop_members[target_shop].add(p)
                heapq.heappush(shop_heap[target_shop], (A[p], p))
            else:
                # 却下
                customer_shop[p] = 0
    
    # 各ショップの会員数を計算
    result = []
    for j in range(1, M+1):
        result.append(str(len(shop_members[j])))
    
    print(" ".join(result))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.