Redial Credits

Medium · hash map

A helpline limits how often each caller can ring in, using credits. Every caller has a bucket that holds at most burst credits. A caller's bucket is full the first time the caller is seen.

Every second that is a multiple of period (that is period, 2 * period, 3 * period, ...), every bucket gains one credit, unless it is already full.

You are given a list of operations in time order. operations[i] is "call" or "reset", and args[i] is [caller, time], where time is the second at which it happens. Times never decrease from one operation to the next. Credits for a second are added before an operation at that same second is handled.

"call": if the caller's bucket holds at least one credit, the call is accepted and uses one credit. Otherwise it is rejected and nothing changes.
"reset": the caller's bucket is filled up to burst at once.

Return a list with one boolean per "call", in the order they appear: true if it was accepted and false if it was rejected. Different callers never affect each other.

Examples

Example 1

Input: burst = 2, period = 5, operations = ["call", "call", "call", "call", "call", "call"], args = [[1, 0], [1, 1], [1, 2], [2, 3], [1, 5], [1, 6]]

Output: [true, true, false, true, true, false]

Caller 1 spends both credits at seconds 0 and 1, so the call at second 2 is rejected. At second 5 one credit is added, so that call is accepted, and the call at second 6 is rejected again. Caller 2 has a bucket of its own.

Example 2

Input: burst = 1, period = 3, operations = ["call", "call", "reset", "call", "call", "call"], args = [[7, 0], [7, 2], [7, 2], [7, 2], [7, 3], [7, 6]]

Output: [true, false, true, true, true]

The second call finds the bucket empty and is rejected. The reset at second 2 fills it, so the next call is accepted. A credit arrives at second 3 and another at second 6, so the last two calls are accepted too.

Constraints

1 <= burst <= 1000
1 <= period <= 1000
1 <= len(operations) <= 5 * 10^4
len(args) == len(operations)
operations[i] is call or reset
0 <= caller <= 10^5
0 <= time <= 10^6, and times never decrease