1920. A Cache Whose Entries Grow Stale

A cache holds at most c entries, and every entry also has a lifetime of L seconds. Three operations arrive, one per line, each carrying the current time:

put k v t store v under k at time t get k t print the value under k at time t, or miss size t print how many entries are alive at time t

An entry written at time w is alive for every time t with w <= t < w + L. At t = w + L it has expired. An expired entry is gone: it is never returned, and it does not occupy one of the c slots.

c = 2, L = 3 put 1 10 1 1 lives for times 1, 2, 3 put 2 20 2 2 lives for times 2, 3, 4 get 1 3 -> 10 get 1 4 -> miss 1 expired at time 4 size 4 -> 1 put 3 30 4 room is free, so nothing is evicted size 4 -> 2

## The two rules that make the answer unique

• Expiry is measured from the last WRITE. A successful get does not extend an
• entry's life.
• A get that hits, and a put of a key already present, both count as a USE,
• which only matters for eviction: when the cache is full and a new key arrives,
• the least recently used LIVE entry is thrown away.

So a hot entry still dies on schedule. That is what a time-to-live is for; a cache that let reads extend lifetimes would serve a stale value forever as long as somebody kept asking for it.

## What most people try first

Purge lazily and nothing else: check an entry's expiry when it is read, and treat it as absent if it has expired. That answers get correctly and answers size wrongly, and worse, it lets dead entries hold slots, so a live key gets evicted to make room while expired keys sit there.

Fixing that by sweeping the whole cache for expired entries on every operation is correct and costs O(c) per operation, about 4 * 10^10 steps with c and q both at 2 * 10^5.

## Two orderings over the same entries

The structure needs to answer two different "which one is oldest" questions, so it keeps two orders:

use order a doubly linked list by last use, for choosing the eviction expiry order a queue of (expiry, key) pairs, for purging

The second one is free. Times arrive non-decreasing, and every entry's expiry is its write time plus the same L, so expiries are produced in non-decreasing order and a plain queue is already sorted. Before each operation, pop from the front of that queue while its expiry is at most t, and delete that entry.

A key written twice leaves a stale pair behind, so each pair is checked against the entry's current expiry before anything is deleted; if they disagree the pair belongs to a version that no longer exists and is simply dropped.

## Why the total work is linear

Each put appends exactly one pair, so the queue receives at most q pairs across the whole run, and each is popped at most once. A single operation may purge many entries, but the total over the run is bounded by the number of pairs ever pushed. That makes purging O(1) amortised, so every operation is amortised constant and the run is O(q).

## Sizes

Times reach 10^9 and L reaches 10^9, so an expiry w + L reaches 2 * 10^9. That still FITS in a signed 32 bit integer, whose limit is 2147483647, but it is close enough to the edge to be worth noticing, and in a language where the addition is done in 32 bits with a larger L it would not. Keys and values reach 10^9 and are never added to anything.

Constraints - `1 ≤ c ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ L ≤ 1000000000` - `1 ≤ t ≤ 1000000000`, non-decreasing across the input - `1 ≤ k ≤ 1000000000` and `0 ≤ v ≤ 1000000000`