Overview

Given the price and capacity of each seating area, along with information about which area each fan attempts to reserve, find the total ticket price of fans who successfully made reservations.

Analysis

The essence of the problem is to process fan reservation requests sequentially while managing the remaining seat count for each area. Each area is independent — even if one area is full, it does not affect other areas. In a straightforward approach, we manage the remaining seat count for each area using an array, and for each incoming fan, we check the remaining seats in the corresponding area and process accordingly. Since the constraints are as large as \(N, M \leq 10^5\), each operation must be performed in constant time.

Algorithm

1. Read the information for each area (price \(C_i\) and capacity \(K_i\))
2. Initialize an array remaining to manage the remaining seat count for each area (initial values are the capacities \(K_i\))
3. Process each fan’s reservation request in order:
   • Compute the index of the requested area \(P_j\) (\(P_j - 1\))
   • If the remaining seat count for the corresponding area is greater than 0:
     • Decrease the remaining seat count by 1
     • Add the price \(C_i\) of that area to the total amount
4. Output the final total amount

Complexity

• Time complexity: \(O(M)\)
  • Since each fan’s reservation can be processed in constant time, processing \(M\) fans takes \(O(M)\) time
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store area information and remaining seat counts

Implementation Notes

• Area numbers are given as 1-indexed, so they need to be converted to 0-indexed when accessing arrays

• Since the input data can be large, use sys.stdin.read() to read all input at once for improved processing efficiency

• Use a simple array to manage remaining seat counts, allowing constant-time access to each area

• The only conditional check needed is “remaining seats > 0” (there is no risk of the value becoming negative)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    
    areas = []
    for _ in range(N):
        c = int(next(it))
        k = int(next(it))
        areas.append((c, k))
    
    bookings = []
    for _ in range(M):
        p = int(next(it))
        bookings.append(p)
    
    remaining = [k for _, k in areas]
    total_revenue = 0
    
    for p in bookings:
        idx = p - 1
        if remaining[idx] > 0:
            remaining[idx] -= 1
            total_revenue += areas[idx][0]
    
    print(total_revenue)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.