1954. A Short Leash And A Long One

A real service rarely has one limit. It has a tight one to stop a burst and a loose one to hold the average down: at most m1 requests in any w1 seconds, AND at most m2 requests in any w2 seconds, with w1 the shorter window.

try t a request arrives at time t; print allow or deny short t print how many allowed requests lie in (t - w1, t] long t print how many allowed requests lie in (t - w2, t]

Timestamps are non-decreasing. An allowed request counts against BOTH limits. A denied request counts against neither.

``` w1 = 2, m1 = 2, w2 = 6, m2 = 3

try 1 -> allow short 1, long 1 try 1 -> allow short 2, long 2 try 1 -> deny the short window is full short 1 -> 2 long 1 -> 2 try 3 -> allow the short window has cleared; long is now 3 short 3 -> 1 long 3 -> 3 try 7 -> allow the long window has cleared too ```

## The two rules worth stating

AND, not OR. A request needs room in both windows. Allowing when either has room is a different limiter and a much weaker one: the long limit would never bind, because the short window almost always has room after a brief pause.

Both or neither. An allowed request is recorded in both windows. Recording it in only the short one makes the long limit permanently empty, so the steady rate is not enforced at all while every short-window test still passes.

## What most people try first

One window and a derived second limit, for instance allowing m1 per w1 and hoping that averages out to m2 per w2. It does not: m1 requests at the start of every w1 block gives m1 * w2 / w1 per long window, which exceeds m2 whenever the long limit is the tighter of the two. The two limits are genuinely independent constraints and both have to be represented.

The second attempt keeps one list of accepted times and filters it twice per question. That is correct, and O(n) per operation.

## Two queues, evicted on every operation

``` A accepted times inside the short window B accepted times inside the long window

on any operation at time t: while A non-empty and A.front <= t - w1: pop A while B non-empty and B.front <= t - w2: pop B try: if |A| < m1 and |B| < m2 -> push t on BOTH, allow otherwise -> deny, push nothing ```

The two queues hold the same values and differ only in how long they keep them, which is why one list filtered twice is also correct and why two queues is faster: each queue evicts in O(1) amortised, while a filter rescans.

## Why it is correct

Each queue independently maintains the invariant from problem 1949: it holds exactly the accepted requests inside its own window, because eviction stops at the first live entry and the stored timestamps are non-decreasing. Since try consults both sizes before pushing to either, the decision sees a consistent view of both limits, and a refusal leaves both untouched.

One consequence is worth noticing: B is always a superset of A, since w2 > w1 means anything live in the short window is live in the long one. So long is never smaller than short, which is a cheap self-check on any implementation.

## The boundary that breaks a careless implementation

Pushing to one queue and not the other, as above. There is a test whose only purpose is a run where the long limit must bind.

The second is using OR rather than AND. On a steady trickle both agree, and they diverge only once the long window has filled while the short one is empty, which takes a specific shape of input to produce.

The third is eviction on the read operations. short and long must evict too, or they report requests that have aged out and disagree with what try would decide at the same instant.

## Overflow

A timestamp reaches 1000000000, which fits in a signed 32 bit integer since the limit is 2147483647, and t - w reaches -1000000000, which also fits since the smallest value is -2147483648. Nothing here is added or multiplied: both windows are only ever subtracted from the current time, so no intermediate grows beyond the inputs.

## Cost

O(1) amortised per operation, since each accepted request is pushed once and popped once in each queue, with O(min(m1 + m2, 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 ≤ w1 < w2 ≤ 1000000000` - `1 ≤ m1 ≤ 200000` and `1 ≤ m2 ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ t ≤ 1000000000`, and timestamps are non-decreasing - every operation runs in `O(1)` amortised, with `O(min(m1 + m2, 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