Overview

For each customer’s budget \(S_i\), we uniquely determine “the highest-priced ticket they can afford,” and if that ticket has been sold fewer than \(K\) times, we sell it. We simulate this process in order from the first customer and count how many people successfully purchase a ticket.

Analysis

• In step 1, the ticket with “the maximum price not exceeding the budget” is selected. Since all ticket prices \(G_j\) are distinct, the selected ticket is always unique.
• More importantly, even if that ticket is sold out, no alternative ticket is sold.
  In other words, for each customer, once we know “the highest-priced ticket among the candidates,” whether or not the sale goes through is determined solely by checking if the number of sales for that ticket is less than \(K\).

A naive approach would, for each customer: - Search for “the maximum \(G_j\) satisfying \(G_j \le S_i\)” by brute force (\(O(M)\))

This gives an overall complexity of \(O(NM)\), which can be up to \(4 \times 10^{10}\) and is too slow.

However, if we sort the ticket prices \(G\) in advance: - “The maximum element not exceeding \(S_i\)” can be found in \(O(\log M)\) using binary search.

Example: When \(G=[100, 250, 400, 1000]\): - If \(S_i=380\), then \(400\) is too expensive, so the maximum is \(250\) - If \(S_i=1000\), the maximum is \(1000\)

These can be found efficiently using binary search.

Algorithm

1. Sort the ticket price array \(G\) in ascending order.
2. Initialize the sales count sold[idx] to 0 for each price (by sorted index).
3. Process each customer’s budget \(s\) in order:
   • Use idx = bisect_right(G, s) - 1 to find the largest idx such that \(G[idx] \le s\)
     (bisect_right returns “the rightmost position where \(s\) could be inserted while maintaining order,” so subtracting 1 gives “the position of the largest element not exceeding \(s\)”)
   • If idx >= 0 (a purchasable ticket exists) and sold[idx] < K (not yet sold out), make the sale:
     • sold[idx] += 1, ans += 1
   • Otherwise, no sale is made (no alternative is sought)
4. Output ans.

Complexity

• Time complexity: \(O(M \log M)\) for sorting, \(O(N \log M)\) for binary search per customer, totaling \(O((N+M)\log M)\)
• Space complexity: \(O(M)\) for the sales count array, etc.

Implementation Notes

• Make sure to check the case where bisect_right(G, s) - 1 results in -1 (when all \(G_j > s\)).

• Prices and budgets can be up to \(10^{18}\), but Python’s int handles this natively.

• “Selling the next cheapest ticket when the desired one is sold out” is not allowed, so when a ticket is sold out, we simply do nothing and move on to the next customer, which is correct.

  Source Code

import sys
from bisect import bisect_right

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    S = list(map(int, input().split()))
    G = sorted(map(int, input().split()))

    sold = [0] * M
    ans = 0

    for s in S:
        idx = bisect_right(G, s) - 1
        if idx >= 0 and sold[idx] < K:
            sold[idx] += 1
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.