Versioned Notes

Medium · binary search

A notes app keeps a history for every key. Each time a value is saved, it is saved together with a time, so older values are never lost. You are given a list of operations. operations[i] is either "set" or "get", and args[i] holds its arguments: [key, value, time] for a "set" and [key, time] for a "get".

"set" saves value for key at the given time.
"get" looks at everything saved for key so far and returns the value that was saved at the latest time that is not after the given time. If nothing was saved for that key at or before that time, it returns -1.

Operations are processed in the order given. For each key, the "set" operations come with strictly increasing times, but a "get" may ask about any time, and the times of different keys are unrelated.

Return a list with the result of every "get", in the order they appear.

Examples

Example 1

Input: operations = ["set", "set", "get", "get", "get"], args = [[1, 10, 5], [1, 20, 8], [1, 4], [1, 6], [1, 9]]

Output: [-1, 10, 20]

Nothing was saved at or before time 4. At time 6 the latest save is the one at time 5. At time 9 it is the one at time 8.

Example 2

Input: operations = ["set", "set", "get", "get", "get"], args = [[7, 3, 1], [2, 4, 1], [7, 1], [2, 100], [9, 1]]

Output: [3, 4, -1]

Each key has its own history, and key 9 has none.

Example 3

Input: operations = ["get", "set", "get"], args = [[1, 5], [1, 6, 2], [1, 5]]

Output: [-1, 6]

The first get comes before anything was saved, so it finds nothing even though it asks about time 5.

Constraints

1 <= len(operations) <= 10^4
len(args) == len(operations)
operations[i] is set or get
0 <= key <= 10^9
0 <= value <= 10^9
0 <= time <= 10^9
For each key, the times of its set operations are strictly increasing in the order given