1950. A Bucket That Refills While You Wait

A bucket holds at most c tokens and gains r tokens per second. A request costs some number of tokens and is served only if the bucket has that many.

take t k at time t, take k tokens if the bucket has at least k; print ok if taken, otherwise no and take nothing tokens t print how many tokens the bucket holds at time t

The bucket starts FULL at time 0, with c tokens. Timestamps are non-decreasing, and every number here is an integer: the bucket gains exactly r tokens for each whole second, never a fraction of one.

``` c = 3, r = 1

tokens 0 -> 3 the bucket starts full take 0 3 -> ok the bucket is now empty tokens 0 -> 0 take 0 1 -> no nothing has accrued at the same instant tokens 2 -> 2 two seconds have passed take 2 2 -> ok tokens 5 -> 3 three seconds would give 3, but the capacity is 3 take 5 3 -> ok ```

## Why this is stated with integers and no fractions

A token bucket is usually written with a fractional level, and then the answer depends on how each language rounds, so five correct-looking solutions disagree about the last token. Here r tokens arrive per whole second and nothing else does, so the level is always an exact integer and the answer is the same everywhere. That is a deliberate restriction on the problem, not an omission.

## What most people try first

A running loop over seconds, adding r each time. Timestamps reach 10^9, so that loop has 10^9 iterations between two requests and never finishes.

The second attempt replays the whole accepted history on every operation to recompute the level. It is correct and it is O(n) per operation, and it is the implementation worth writing once as a check, because the level really is determined by the history rather than by anything cleverer.

## Accrue once, lazily, then decide

Keep the level and the time it was last brought up to date. Nothing has to happen between operations.

``` tok tokens in the bucket, exact last the time tok refers to

on any operation at time t: tok = min(c, tok + (t - last) * r) last = t then serve the operation ```

## Why it is correct

The level never needs to be known at a time when nothing happens, so computing it only at operations loses nothing. Between last and t no tokens are spent, so the level rises by exactly (t - last) * r and is then clipped by the capacity. Clipping once at the end is the same as clipping continuously, because the level only rises during that interval: if it would exceed c at any point inside, it is still at c at the end, and if it never does, the clip does nothing.

That argument fails the moment spending can happen inside the interval, which is exactly why the accrual must be done BEFORE the request is served and not after.

## The boundary that breaks a careless implementation

Forgetting the capacity. An idle hour then banks an hour of tokens and a later burst is served that should not be, which no test without an idle gap can see.

The other one is order. Serving the request and then accruing uses a level that is one accrual stale, so a take at the same instant as the accrual is refused when it should succeed. Both reorderings are invisible on a stream whose requests arrive one per second.

A take of zero tokens must succeed, including from an empty bucket, since zero is never more than the level.

## Overflow

This is where the problem has real teeth. A timestamp gap reaches 10^9 and r reaches 10^9, so the accrual (t - last) * r reaches 10^18. That does NOT fit in a signed 32 bit integer, whose largest value is 2147483647, so the accrual and the level must be 64 bit, where the limit is about 9.2 * 10^18. The product is the only large intermediate: once it is clipped to c, the level is back under 10^9.

JavaScript is an interesting case here, and the honest answer is narrower than the usual warning. A Number is an exact integer only below 2^53, which is 9007199254740992, so a product near 10^18 may be rounded: 999999999 * 999999999 is 999999998000000001 exactly and 999999998000000000 as a Number. That rounding does not change any answer in THIS problem, because the product is immediately clipped to the capacity and any value at or above c clips to the same c. The 32 bit case is the one that genuinely bites: 10^18 wrapped to 32 bits is -1486618624, a NEGATIVE level, which the clip does not catch, so every later request is wrongly refused.

If you want the product never to be large at all, cap it as soon as it exceeds c: the accrual only ever matters up to the capacity.

## Cost

O(1) per operation and O(1) memory. the judge cannot enforce that: the declared tests are small and there is no test generator yet, so rescanning the whole accepted history on every operation passes them while doing about 4 * 10^10 comparisons at the stated limits.

Constraints - `1 ≤ c ≤ 1000000000` - `0 ≤ r ≤ 1000000000` - `1 ≤ q ≤ 200000` - `0 ≤ t ≤ 1000000000`, and timestamps are non-decreasing - `0 ≤ k ≤ 1000000000` - the bucket gains exactly `r` tokens per whole second, so the level is always an exact integer - every operation runs in `O(1)` with `O(1)` memory