1951. A Queue That Drains At A Fixed Rate

Work arrives and waits. The queue drains at exactly r items per second and holds at most cap items; an arrival that finds the queue full is dropped rather than refused politely.

arrive t an item arrives at time t; print queued or dropped pending t print how many items are still waiting at time t clear t print how many whole seconds from t until the queue is empty, or never if it can never empty

The queue starts empty at time 0 and timestamps are non-decreasing. Draining happens by whole items at whole seconds, so the pending count is always an exact integer.

``` cap = 3, r = 1

arrive 0 -> queued 1 waiting arrive 0 -> queued 2 waiting arrive 0 -> queued 3 waiting arrive 0 -> dropped the queue is full pending 0 -> 3 clear 0 -> 3 pending 2 -> 1 two seconds have drained two items clear 2 -> 1 ```

## This is the opposite trade from a limiter

A sliding window limiter refuses the excess and keeps nothing. A leaky bucket ACCEPTS the excess, up to its capacity, and makes it wait. So the interesting question flips from "was this allowed" to "how far behind are we", and the only thing that is ever refused is an arrival with nowhere to sit.

## What most people try first

Draining in a loop, one second at a time. The gap between arrivals reaches 10^9 seconds, so the loop never finishes.

The second attempt drains lazily, which is right, and forgets that the level cannot go below zero. After a long idle period the computed level is a large negative number, so the queue then absorbs a burst far larger than its capacity, and pending prints a negative count. The floor is the whole of the correctness here.

## Drain lazily, then floor at zero

``` pend items waiting, exact last the time pend refers to

on any operation at time t: pend = max(0, pend - (t - last) * r) last = t ```

clear is then a division, rounded UP: with pend items and r per second, the queue is empty after ceil(pend / r) seconds, which in integers is (pend + r - 1) / r. Rounding down would report a time at which items are still waiting.

## Why it is correct

Between two operations nothing arrives, so the level only falls, and it falls at exactly r per second until it reaches zero and stays there. Subtracting the whole interval and then flooring gives the same result as flooring continuously, precisely because the level never rises in between: once it hits zero it cannot leave, so clamping at the end is equivalent.

That argument is the mirror image of the token bucket in problem 1950, where the level only RISES between operations and is therefore clipped at the top instead. Both are correct for the same reason and both break if an arrival could happen inside the interval.

## The boundary that breaks a careless implementation

The floor at zero, as above. And the rounding direction in clear: with 1 item left and a rate of 2 per second, the answer is 1 second, not 0.

A rate of zero is legal and must be handled rather than dividing by it: the queue never drains, so clear prints never when anything is waiting and 0 when nothing is.

## Overflow

The drain (t - last) * r reaches 10^9 * 10^9 = 10^18, which does not fit in a signed 32 bit integer whose limit is 2147483647. Wrapped to 32 bits it can come out positive, which makes the subtraction underflow into a large positive level rather than zero, so the queue then drops everything. Hold the product in a 64 bit type, where the limit is about 9.2 * 10^18, or cap it at cap as soon as it exceeds it, since draining more than the whole queue is the same as draining the whole queue.

## Cost

O(1) per operation and O(1) memory, with no loop over seconds anywhere. 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 ≤ cap ≤ 1000000000 - 0 ≤ r ≤ 1000000000 - 1 ≤ q ≤ 200000 - 0 ≤ t ≤ 1000000000, and timestamps are non-decreasing - draining happens by whole items at whole seconds, so the pending count is always an exact integer - every operation runs in O(1) with O(1) memory