1916. A Store That Remembers When

Build a key-value store where every write carries a timestamp and a read asks for the value as of a given time.

set key value t record that key had this value at time t get key t print the value key had at the largest recorded time <= t

If the key was never set at or before t, print none. Timestamps for a given key are strictly increasing across the input.

## What most people try first

A normal map from key to value. It answers "what is this key now" and that is the wrong question: a historical read at t cannot be answered at all once a later write has overwritten the value, and the only reason it ever looks right is that a test which reads after the last write agrees with it by accident.

The second attempt keeps every write for a key in a list and scans it. That is correct, and it is O(writes) per read, so a key written 100000 times and read 100000 times costs about 10^10 comparisons.

## Binary search over the per-key history

Because each key's timestamps arrive strictly increasing, that key's list is already sorted, with no sorting step anywhere. A read is then the largest timestamp not exceeding t, which is a lower bound search:

``` key k: times 1 5 9 values a b c

get k 2 -> first time greater than 2 is 5, at index 1 step back one -> index 0 -> a get k 5 -> first time greater than 5 is 9, at index 2 step back one -> index 1 -> b get k 0 -> first time greater than 0 is 1, at index 0 step back one -> index -1 -> none ```

This is the same search as in the binary search topic, applied to a structure rather than to one array.

## Why it is correct

Search for the first index whose timestamp is strictly greater than t. Every index before it has a timestamp at most t, and the timestamps increase, so the one immediately before it is the largest such timestamp and therefore the newest value in force at time t. If that index is 0, no write happened at or before t, which is exactly the none case. The invariant that makes this work is that the list is sorted, and it is sorted because the input promises strictly increasing timestamps per key, not because anything sorted it.

Keys are independent: a write to one key can never change any answer about another, which is why the histories are stored per key rather than in one log.

## The boundary that breaks a careless implementation

The strictness of the comparison. Searching for the first timestamp greater than or equal to t and then stepping back returns the PREVIOUS value whenever t was itself written, so a read at an exact write time is one value stale. That is one word of difference in the code and it has two tests.

The other case is the empty history. A key never written must print none rather than reaching into an absent list, and a key written only in the future of t must also print none rather than its first value.

## Overflow

A timestamp reaches 1000000000, which fits in a signed 32 bit integer whose largest value is 2147483647. Timestamps are only compared here, never added, so nothing widens; adding two of them would reach 2 * 10^9 and is never needed. The index arithmetic in the search is the usual trap: write the midpoint as lo + (hi - lo) / 2 rather than (lo + hi) / 2 out of habit, even though at 200000 entries the sum cannot overflow here.

## Cost

O(1) amortised for set, because a write only appends to the end of a list, and O(log w) for get where w is the number of writes to that key. Total O(q log q) time and O(q) memory. The judge cannot enforce the per-read bound, so the linear scan passes every declared test; the 10^10 figure above is what it costs at the stated limit.

Constraints - `1 ≤ q ≤ 200000` - `1 ≤ t ≤ 1000000000` - Keys and values are 1 to 20 lowercase English letters or digits. - For any one key, the timestamps given to `set` strictly increase.