A single key's history is stored as two parallel lists: times (strictly increasing) and values, where values[i] was written at times[i] and stayed current until the next write.
Write value_at(times: list[int], values: list[str], t: int) -> str | None that returns the value that was current at time t: the one written at the latest time <= t. If nothing had been written yet by time t, return None.
times = [1, 4, 9]
values = ["red", "green", "blue"]
value_at(times, values, 5) # "green" (written at 4, still current at 5)
value_at(times, values, 4) # "green" (a write at exactly t counts)
value_at(times, values, 0) # None (before the first write)
value_at(times, values, 50) # "blue"
Constraints: up to 100,000 entries, timestamps may be negative, and the lists may be empty. The tests make 100,000 queries on one long history, so scanning the list each time is too slow: use binary search via the bisect module.
Show hint
i = bisect.bisect_right(times, t) is the number of writes at or before t, so the answer is values[i - 1] when i > 0, and None otherwise.