Implement TimeMap, a key-value store that remembers every version of each key:
set(key, value, timestamp): storevalueforkeyas oftimestamp.get(key, timestamp): return the value from thesetonkeywith the largest timestamp<= timestamp, or""if there is none (unknown key, or every version is newer).
For all set calls, timestamps are strictly increasing across the whole store, so each key's history is appended already sorted.
tm = TimeMap()
tm.set("door", "open", 5)
tm.set("door", "shut", 9)
tm.get("door", 4) # "" (nothing that early)
tm.get("door", 5) # "open"
tm.get("door", 8) # "open"
tm.get("door", 100) # "shut"
tm.get("lamp", 7) # ""
Constraints: timestamps up to 10**7; up to ~10^5 calls, possibly all on one key. Scanning a key's whole history per get is O(n) per call, which is too slow: aim for O(log n) per get.
Show hint
Because timestamps only increase, appending to per-key lists keeps each key's history sorted, so get can binary-search it (bisect_right).