1932. How Many Keys Are Still Alive

Every entry in this store carries its own lifetime. Three operations arrive, one per line, and each one states the time it happens at:

set t k v d at time t, store value v under key k with a lifetime of d get t k at time t, print the value stored under k size t at time t, print how many keys are still alive

6 set 1 7 100 5 -> key 7 holds 100 and dies at time 6 set 2 8 200 2 -> key 8 holds 200 and dies at time 4 size 3 -> 2 get 4 8 -> expired time 4 is exactly when key 8 died size 5 -> 1 get 9 7 -> expired

## The rules, stated so the answer is decidable

• set prints nothing. get and size each print one line.
• An entry written at time t with lifetime d is alive for every time now
• with t <= now < t + d. It is NOT alive at now = t + d: the lifetime is how
• long it lasts, so an entry written at time 1 with a lifetime of 5 is gone by
• time 6. Getting that boundary the other way changes the answer to almost
• every test here.
• get prints the value if the key is alive, the word expired if that key was
• stored at some point but has no live entry now, and the word miss if the key
• was never stored at all. Those are three different answers.
• A set on a key that is alive replaces both its value and its death time. A
• set on a key that has expired brings it back, and get then prints the new
• value rather than expired.
• size counts keys, not writes. A key written three times is one key.
• The times given across the whole input never decrease, though two
• consecutive operations may share a time.
• d is at least 1, so no entry is born dead.

Problem 1916 is a store that remembers every version and never expires anything, and problem 1920 is a cache whose entries both expire and get evicted. Neither has to report a count, and that is the whole difficulty here.

## What most people try first

Keep a map from key to value and death time, and check the death time when a key is read. That is correct for get and it cannot answer size, because size depends on keys nobody has asked about. Sweeping the whole map on every size fixes it and costs O(n) per call: with q at 2 * 10^5 and a size every other line, that is about 10^10 checks.

## Expire eagerly, in death order, with a heap

alive a map from key -> (value, death time) ever the set of keys that have ever been stored deaths a min-heap of (death time, key) live a running count of the keys in alive

Before every operation, at its stated time now, pop the heap while its smallest death time is <= now. Each popped pair names a key and a death time; if the map's current entry for that key records exactly that death time, the entry really is this one, so remove it and drop live by one. If it records a different death time, the key was rewritten after this pair was pushed and this pair is stale, so throw it away and change nothing.

## Why it is correct

The clock never goes backwards, so once now has passed an entry's death time that entry can never be alive again, and expiring it eagerly can never be premature. Every write pushes exactly one pair, so a key that was rewritten has several pairs in the heap; the death-time comparison is what tells the live one from the stale ones, and it works because a pair's death time is fixed when the pair is created while the map always holds the latest. After the purge the map holds exactly the live entries, so live is exact and size is one read.

The three answers from get fall out of the two containers: in alive means live, in ever but not alive means expired, in neither means never stored.

## Why it is fast

Each set pushes one pair and each pair is popped at most once, so the purge loop runs at most q times across the whole run. Every operation is therefore O(log q) amortised, and size is O(1).

## Overflow

A time reaches 10^9 and a lifetime reaches 10^9, so a death time reaches 2 * 10^9. That FITS in a signed 32 bit integer, whose limit is 2147483647, but only just, and t + d is the one sum in this problem that gets close. A third addition would not fit, so prefer 64 bit for death times rather than reasoning about the margin. Values reach 10^9 and are never summed.

## Cost

O(q log q) in total, with memory proportional to the number of writes.

Constraints - `1 ≤ q ≤ 200000` - `1 ≤ t ≤ 1000000000`, and the times across the input never decrease - `1 ≤ k ≤ 1000000000` - `0 ≤ v ≤ 1000000000` - `1 ≤ d ≤ 1000000000` - the store starts empty - `set` and `get` must run in amortised `O(log q)` and `size` in `O(1)`, so the whole run is `O(q log q)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so sweeping the whole map on every `size` passes them while doing about `10^10` checks at `q = 200000`