1949. A Limit Over The Last w Seconds

A service allows at most m requests in any window of w seconds. Unlike a fixed block limiter, the window moves with the request: a request at time t is allowed when fewer than m requests were allowed in (t - w, t].

try t a request arrives at time t; print allow or deny count t print how many allowed requests lie in (t - w, t]

Timestamps are non-decreasing. A request at exactly t - w has aged out.

## The rule that makes this a limiter and not a counter

A DENIED request is not recorded. It never enters the window and therefore cannot delay a later request.

That single rule is the whole difference between this problem and problem 1913, the hit counter, which records everything and only answers how many are in the window. Here the answer feeds back into the state: denying changes nothing, so a client hammering a closed limiter is not punished for it. A solution that records every request instead passes a run with no denials at all and then diverges the moment one happens.

``` w = 3, m = 2

try 1 -> allow window holds 1 try 2 -> allow window holds 1 2 try 3 -> deny two in (0, 3], and 3 is not recorded count 3 -> 2 try 4 -> allow 1 has aged out of (1, 4], so one slot is free count 5 -> 2 window (2, 5] holds 4 and... 2 aged out at 5, so 4 only ```

## What most people try first

Keep every allowed request in a list and count the ones inside the window on each operation. It is correct, and it is O(n) per operation, so 200000 operations cost about 4 * 10^10 comparisons.

## A queue, because requests age out in arrival order

Timestamps are non-decreasing, so the allowed requests leave the window in exactly the order they entered it. That is what makes a plain queue sufficient: discard from the front while the oldest has aged out, and the size is the count.

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, allow otherwise -> deny, and push nothing count: the size

## Why it is correct

The queue holds exactly the allowed requests inside (t - w, t]. Discarding stops at the first request still inside, and because the stored timestamps are non-decreasing, everything behind it is at least as new and therefore also inside, so nothing live is ever thrown away. Conversely nothing stale survives, because the loop runs to completion before the size is read.

The total work is linear even though one count can discard many entries: each allowed request is pushed once and popped at most once over the entire run, so the discards add up to O(q) however they cluster.

## The boundary that breaks a careless implementation

The comparison. Discarding while the front is < t - w keeps a request at exactly t - w, which has aged out, so the limiter refuses one request too many and count is one too high for exactly one operation.

The other case is a tie: several requests at the same timestamp. The first m of them are allowed and the rest denied, which is only correct if denials are not recorded.

## Overflow

A timestamp reaches 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. The expression t - w can be as low as -1000000000, which also fits, since the smallest signed 32 bit value is -2147483648, so the comparison needs no widening. Adding two timestamps would reach 2 * 10^9 and is never needed here.

## Cost

O(1) amortised per operation, O(q) time overall, and O(min(m, q)) memory, since the queue never holds more than m entries. 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