1953. Not Just No, But When

A sliding window limiter allows at most m requests in (t - w, t]. This one must also answer the question a client actually wants answered: if not now, when?

try t a request arrives at time t. Print ok if it is allowed, otherwise print the earliest time at which a request WOULD be allowed when t print the earliest time from t onwards at which a request would be allowed, which is t itself when one would be allowed now. This operation changes nothing.

Timestamps are non-decreasing, and a denied request is not recorded.

``` w = 3, m = 2

when 0 -> 0 nothing has arrived, so now is fine try 1 -> ok try 2 -> ok when 2 -> 4 the window holds 1 and 2; time 4 is when 1 falls out try 2 -> 4 denied, and reports the same time when 3 -> 4 try 4 -> ok 1 has aged out try 5 -> ok 2 has aged out ```

## Why the answer is the oldest live request plus w

The window (t - w, t] excludes its left endpoint, so a request made at time e is live at time t exactly while t < e + w, and has aged out from e + w onwards.

When the limiter is full there are exactly m live requests. A later request is allowed as soon as one of them leaves, and the first to leave is the oldest, at time oldest + w. So the answer is oldest + w and not one instant later or earlier.

That is the part a plain counter cannot do. Counting tells you how many are in the window; it does not tell you WHEN the next one departs, so this problem forces the actual timestamps to be kept.

## What most people try first

The newest request plus the window. It reads plausibly, since the newest request is the one that filled the limiter, and it is far too late: it waits for the whole window to clear rather than for one slot to free up. On a burst of m requests at the same instant the two answers coincide, which is exactly the shape of the first test anyone writes.

The second attempt is one instant early: oldest + w - 1. At that time the oldest request is still live, because t < e + w still holds, so a request then would be refused again. Reporting a retry time at which the retry fails is worse than reporting nothing.

## A queue, read from the front

The structure is the sliding window queue of problem 1949. The one addition is that the FRONT of the queue is now part of the answer rather than only part of the eviction test.

on any operation at time t: while the queue is non-empty and front <= t - w: pop the front try: if size < m -> push t, print ok otherwise -> print front + w, push nothing when: if size < m -> print t otherwise -> print front + w

## Why it is correct

After eviction the queue holds exactly the live requests, oldest first, because the stored timestamps are non-decreasing. If it holds fewer than m the request is allowed now. If it holds m, then at every time t' with t <= t' < front + w all m are still live, so a request is refused; and at t' = front + w the oldest has departed, leaving m - 1 live, so a request is allowed. That makes front + w the earliest, which is what is asked for.

It also follows that when must not modify anything: it reports a hypothetical, and recording it would change the very answer it just gave.

## The boundary that breaks a careless implementation

when on an empty limiter must print t, not 0 and not a time in the past. And when when the limiter has room must also print t, since now is the earliest possible answer.

The other case is a denied try, which must report the time AND record nothing. A solution that pushes before checking reports a retry time computed from a request that was never accepted.

## Overflow

This is the one problem in the pattern that ADDS two large values rather than comparing them, so the sum is worth computing rather than waving at.

The answer is front + w. Both are at most 1000000000, so the sum is at most 2000000000. A signed 32 bit integer holds up to 2147483647, so every answer here fits, with about seven percent to spare. The margin is the point: raise the window bound to 1500000000 and the identical code overflows, so the safety comes from the constraint rather than from anything in the method. A 64 bit accumulator costs nothing and removes the dependence.

## Cost

O(1) amortised per operation, O(min(m, q)) 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 ≤ w ≤ 1000000000` - `1 ≤ m ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ t ≤ 1000000000`, and timestamps are non-decreasing - every operation runs in `O(1)` amortised, with `O(min(m, q))` 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