What was the value then
Answer many questions of the form "what was the latest value at or before time t" by searching a sorted list of times. About 12 minutes.
The latest update before t
A sensor records a value now and then: at time 3 it read 10, at time 7 it read 25, and so on. The times are sorted. What was the reading at time 8? It is the value from the latest update that happened at or before 8, which is the update at time 7.
That update is the last one whose time is at most t. Search for the first time that is greater than t; the update just before it is your answer. If that first greater time is the very first one, nothing had been recorded yet.
pos = bisect_right(times, t) - 1 # the last time at or before t
Question 7: the last time at most 7 is 6, at position 1. Its value is 15.
One search per question
Each question needs its own search of the same sorted times, so a thousand questions cost a thousand quick searches. You never loop through the whole timeline for each question.
Return the answers in the order the questions were asked. Use the position from the search to look up the value in the matching list, or -1 when the position is before the first update.
if pos >= 0:
answer = values[pos]
else:
answer = -1 # nothing yetA question time equals an update time. Which value do you report?
- AThat update's value, since at or before includes equal
- BThe update before it
- C-1
Show the answer
That update's value, since at or before includes equal. The update happened at exactly that time, so it is the latest one that counts.
What was the value then
A log records that the value became values[i] at time times[i]. The times are strictly increasing, and the value stays the same until the next record. For each question time in queries, return the value that was in effect at that time, meaning the value of the latest record at or before it, or -1 if the time is earlier than every record. Give the answers in the order of the questions.
times = [3, 7, 12], values = [10, 25, 40], queries = [8, 2, 12] → [25, -1, 40]
0 ≤ records ≤ 100,000 · 0 ≤ queries ≤ 3,000 · times strictly increasing