Lemonade Store Limits
MediumState Machines · Optiver
A lemonade chain caps how much product each store may have on outstanding orders. Every store has the same cap, limit (in cups). Process events in order:
[order_id, "ORDER", store_id, beverage, quantity]: a request forquantitycups atstore_id. Accept it if that store's outstanding quantity plusquantityis at mostlimit; otherwise reject it.beverageis informational only; all beverages share the store's cap.[event_id, "CANCEL", order_id]: cancel an earlier order. Iforder_idwas accepted and has not been cancelled yet, its quantity stops counting toward its store's outstanding total. Cancelling an unknown order, a rejected order, or an already-cancelled order does nothing.
A store's outstanding quantity is the total of its accepted orders that have not been cancelled. Stores are independent.
Return the ids of accepted orders, in the order they were accepted.
Example 1
- Input:
- limit = 10, events = [["o1", "ORDER", "soho", "lemonade", 6], ["o2", "ORDER", "soho", "iced tea", 5], ["o3", "ORDER", "tribeca", "lemonade", 9], ["c1", "CANCEL", "o1"], ["o4", "ORDER", "soho", "lemonade", 10]]
- Output:
- ["o1", "o3", "o4"]
- Explanation
o2would take Soho to 11, over the cap of 10, so it is rejected. Tribeca is a separate store, soo3fits. Cancellingo1drops Soho back to 0, ando4fits exactly at 10.
Example 2
- Input:
- limit = 5, events = [["o1", "ORDER", "s", "tea", 5], ["o2", "ORDER", "s", "tea", 2], ["c1", "CANCEL", "o2"], ["c2", "CANCEL", "nope"], ["o3", "ORDER", "s", "tea", 1]]
- Output:
- ["o1"]
- Explanation
o2was rejected, so cancelling it frees nothing, andnopenever existed. The store is still at 5, soo3is rejected.
Example 3
- Input:
- limit = 4, events = [["a", "ORDER", "s", "x", 3], ["c1", "CANCEL", "a"], ["c2", "CANCEL", "a"], ["b", "ORDER", "s", "x", 4], ["c", "ORDER", "s", "x", 1]]
- Output:
- ["a", "b"]
- Explanation
- The second cancel of
ais a no-op, so the outstanding total never goes negative.bfills the store to 4 andcis rejected.
Constraints
- 0 ≤ events.length ≤ 105
- 0 ≤ limit ≤ 109
- 0 ≤ quantity ≤ 109
- All order ids and event ids are distinct strings.