Overview

This is a simulation problem where you process \(N\) customers in order, find the most expensive ticket within each customer’s budget, and sell that ticket if its sales count has not yet reached the limit \(K\).

Analysis

Key Observation

For each customer, the following two operations are performed:

1. Find the most expensive ticket within the budget (searching for the maximum)
2. Check the number of tickets already sold for that ticket, and sell if less than \(K\) (count management)

An important point is that even if the ticket found in step 1 is sold out (\(K\) tickets already sold), no alternative ticket is sold instead. In other words, there is at most one candidate ticket type for each customer.

Problem with the Naive Approach

If you scan all tickets each time without sorting the ticket prices, it becomes \(O(NM)\), and when \(N, M\) are up to \(2 \times 10^5\), this requires \(4 \times 10^{10}\) operations, resulting in TLE.

Solution

By sorting the ticket prices in advance, for each customer’s budget \(S_i\), you can find “the maximum value less than or equal to \(S_i\)” using binary search in \(O(\log M)\). This speeds up the overall complexity to \(O(N \log M)\).

Algorithm

1. Sort the ticket price array \(G\).
2. Prepare a dictionary (hash map) to manage the number of tickets sold for each ticket price, initializing all to \(0\).
3. Process customers from the \(1\)st to the \(N\)th in order:
   • Use bisect_right(G_sorted, S_i) - 1 to find the index pos of the maximum ticket price less than or equal to \(S_i\).
   • If pos < 0, no ticket exists within the budget, so skip.
   • If pos >= 0, check the number of tickets sold for that ticket price ticket_price = G_sorted[pos].
     • If less than \(K\), sell the ticket, increment the count by \(+1\), and also increment the answer by \(+1\).
     • If \(K\) or more, skip (no alternative ticket is sold).
4. Output the final answer.

Concrete Example

For \(N=3, M=2, K=1\), budgets \(S = [500, 300, 400]\), ticket prices \(G = [200, 400]\):

• After sorting: \(G_{\text{sorted}} = [200, 400]\)
• Customer 1 (budget 500): \(400 \leq 500\) is the maximum → Sell ticket 400 (0 remaining) ✓
• Customer 2 (budget 300): \(200 \leq 300\) is the maximum → Sell ticket 200 (0 remaining) ✓
• Customer 3 (budget 400): \(400 \leq 400\) is the maximum → Ticket 400 is sold out (\(K=1\) tickets) → Skip ✗

Answer: 2

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • \(O(M \log M)\) for sorting ticket prices, \(O(\log M)\) × \(N\) customers for binary search per customer
• Space complexity: \(O(M + N)\)
  • Sorted ticket array, dictionary for sales counts, and customer budget array

Implementation Notes

• Usage of bisect_right: bisect_right(G_sorted, s) returns “the smallest index greater than \(s\)”, so subtracting \(1\) from it gives “the index of the largest element less than or equal to \(s\)”. If the result is \(-1\), there is no matching ticket.

• Managing sales counts: Since all ticket prices are distinct, sales counts can be managed using a dictionary with prices as keys.

• Value ranges: Although \(S_i, G_j\) can be as large as \(10^{18}\), in Python there is no need to worry about integer overflow, so they can be handled as-is.

  Source Code

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    S = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    G = [int(input_data[idx + i]) for i in range(M)]
    idx += M
    
    # Sort G and use a SortedList for available tickets
    # We need to find the largest G_j <= S_i
    # Each ticket can be sold at most K times
    
    G_sorted = sorted(G)
    
    # We'll use binary search on sorted G to find the ticket
    # and maintain a count array
    import bisect
    
    count = {}
    for g in G:
        count[g] = 0
    
    ans = 0
    
    for i in range(N):
        s = S[i]
        # Find largest G_j <= s
        pos = bisect.bisect_right(G_sorted, s) - 1
        if pos < 0:
            continue
        ticket_price = G_sorted[pos]
        if count[ticket_price] < K:
            count[ticket_price] += 1
            ans += 1
        # If already K sold, do not sell (no fallback)
    
    print(ans)

main()

---

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