Settings Log With Time Travel

Design a class SettingsLog that remembers every value a setting has ever had and can answer what the setting was at any moment:

• SettingsLog() starts empty.
• set(key, value, t) records that key took the value value at time t. Across all set calls the times are strictly increasing.
• get(key, t) returns the value recorded for key with the largest time that is <= t. If key was never set, or was only set after t, return the empty string "".

Examples

ops:  ["SettingsLog", "set", "get", "get", "set", "get", "get", "get"]
args: [[], ["theme", "dark", 5], ["theme", 4], ["theme", 5], ["theme", "light", 9], ["theme", 8], ["theme", 12], ["font", 12]]
Output: [None, None, "", "dark", None, "dark", "light", ""]
Explanation: at time 4 the theme had not been set yet; at 8 it was still "dark"; "font" was never set.

Constraints

• Keys are short strings; values are strings or integers; 0 <= t <= 10**9
• Up to 10**4 calls in total; get times are arbitrary (not necessarily increasing)
• Target: set in O(1) amortised, get in O(log h) where h is the number of values stored for that key

Goals

• Keep a sorted history per key so that past values can be looked up
• Answer 'value as of time t' with binary search instead of a scan