1948. A Limit That Resets On The Hour

A service allows at most m requests per window of w seconds. Time is cut into fixed blocks starting at zero, so the blocks are [0, w), [w, 2w) and so on, and the count resets to zero at every block boundary.

try t a request arrives at time t; print allow or deny count t print how many requests have been allowed in the block holding t

Timestamps are non-decreasing. A DENIED request is not recorded and does not count against the limit.

## The two rules that make this answerable

A timestamp exactly on a boundary belongs to the NEW block: time w is the first instant of the second block, not the last of the first. That is what integer division by w gives, and it is stated because the other reading is equally defensible and produces different output.

A denied request is not recorded. Without that rule a burst of refusals would keep the limiter shut, which is a real design but a different one.

``` w = 3, m = 2

try 0 -> allow block 0, count 1 try 1 -> allow block 0, count 2 try 2 -> deny block 0 is full count 2 -> 2 try 3 -> allow time 3 starts block 1, so the count has reset count 3 -> 1 ```

## What most people try first

A sliding window: keep the last w seconds of requests and count them. It is the more useful limiter in practice and it is not this one. A sliding window never resets, so after try 0 and try 1 above it would still deny at time 3, because two requests sit within the last 3 seconds. The two designs agree on smooth traffic and disagree on exactly the inputs anyone would test with, which is why the block rule is written into the statement rather than left to intuition.

The second mistake is to keep a list of allowed timestamps and count the ones in the current block. That is correct, and it is O(n) per operation.

## One block index and one counter

Nothing more is needed. Since timestamps never go backwards, once a request arrives in a later block, every earlier block is finished forever.

``` cur the block the counter currently describes, -1 before anything arrives cnt how many requests have been allowed in block cur

on any operation at time t: blk = t / w integer division if blk != cur: cur = blk ; cnt = 0 ```

## Why it is correct

The reset is sound because the timestamps are non-decreasing: a request in block blk can never be followed by one in an earlier block, so the count for cur is complete the moment the block changes and may be discarded. That is the whole reason this needs constant memory while a sliding window needs a queue.

The division is exact rather than approximate. t / w rounded down is the index of the unique block containing t, because the blocks are the intervals [k*w, (k+1)*w) and k*w <= t < (k+1)*w holds exactly when k is that quotient.

## The boundary that breaks a careless implementation

A request at exactly t = w, 2w and so on. It must start a new block, so a solution comparing t - start < w with a start it forgot to advance keeps counting into the old block.

The other case is count before anything has arrived, which must print 0, and count in a block where everything was denied, which must also print 0.

## Overflow

A timestamp reaches 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647. The block index t / w is at most the timestamp, so it fits too. Nothing multiplies a timestamp here; computing blk * w would reach the same magnitude and is never needed, which is worth noticing because that product is how this problem usually acquires an overflow it does not need.

## Cost

O(1) per operation and O(1) memory, which is the striking part: the limiter needs no history at all. 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 ≤ 1000000000` - `1 ≤ q ≤ 200000` - `0 ≤ t ≤ 1000000000`, and timestamps are non-decreasing - every operation runs in `O(1)` with `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