Seismic watch
After a strong earthquake seismologists wait for aftershocks and declare a watch in the region. The stronger the shock, the longer the watch. A new shock in the same region may extend the watch, and the duty officer may lift it early. The control room needs a log: when and in which region a watch ended by itself, without being cancelled.
Events come in time order. An earthquake Q t r d in region r at time t requires the watch in the region to last at least until t + d: if there is no watch, one starts; if it ends earlier, it is extended to t + d; if later, nothing changes. A cancellation C t r lifts the watch in region r if one is in force. A watch that ends at time e ends before all events at time e: a shock at that same time opens a new watch in the region, and a cancellation at that same time no longer lifts anything.
One of the tests is the real USGS catalogue: 19,073 earthquakes of magnitude 5 and above in 2015–2025. A region is a 10° × 10° cell of latitude and longitude, time is in seconds since the start of 2015, and a watch lasts two days after a magnitude 5 shock and four times longer for each further unit of magnitude.
Input
The first line holds n (1 ≤ n ≤ 100,000), the number of events. Then n lines, each Q t r d or C t r, where 0 ≤ t ≤ 10⁹, 1 ≤ r ≤ 10⁹, 1 ≤ d ≤ 10⁹. The times t do not decrease.
Output
For each watch that ended by itself, a line e r: the end time and the region number. The lines go in increasing order of e, and for equal e in increasing order of region number. Watches still in force after the last event also end by themselves at their times; print them too. If there are no such watches, print nothing.
Examples
Example 1
7 Q 0 7 100 Q 30 3 50 Q 60 7 100 C 70 3 Q 75 3 10 Q 90 5 20 Q 100 5 5
85 3 110 5 160 7
Example 2
6 Q 0 2 10 Q 0 1 10 Q 10 2 5 Q 12 9 3 Q 15 4 1 C 15 9
10 1 10 2 15 2 15 9 16 4
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A watch may be extended many times. How many entries should you keep for it, and what should you do with the old entry when the end has moved? You do not have to find it.
2Hint 2
Keep a heap of pairs (end, region) and a dictionary “region → current end of the watch”. When a pair surfaces at the top, how can you tell whether it still means anything?
3The idea
This is an event calendar with lazy deletion. Every extension pushes a new pair into the heap, and the old one stays where it is. A cancellation only erases the region from the dictionary. A pair is current if its end matches the current end of the watch in the dictionary; extended and cancelled watches fail this check, and their pairs are thrown away when they surface. Before each event, take from the heap all pairs with an end no later than the event's time: these are the watches that ended before it.
4Walkthrough
The order of actions at each event: first close everything that ended by time t, then apply the event itself. That way the condition “a watch ends before the events of its own time” holds by itself. Pairs are compared first by end, then by region, so they leave the heap in exactly the order they must be printed. After the last event close everything that is left.
The check “the end matches” is enough. An extended watch has a larger end in the dictionary, a cancelled one has no entry. It can happen that a watch is cancelled and immediately reopened with the same end; then the heap holds two identical pairs: the first is printed and erases the region, and the second no longer finds it in the dictionary.
If you read all the events in advance, you can do without a heap: go through them, compute the end time of each watch and sort the ends. The heap is needed when the log has to be kept as things happen, without knowing future events, as in a real control room.
4+Solution
5Complexity
Each earthquake pushes at most one pair into the heap, and each pair is taken out once: O(n log n) time and O(n) memory.
6Common mistakes
- Not checking whether a pair is current. An extended watch then “ends” twice. In the first sample such a solution prints the extra lines 80 3 and 100 7.
- The event first, then closing. In the second sample the watch in region 2 ends at time 10, and a shock at that same time must open a new watch, not extend the old one.
- Going through all watches before each event. The answers are right, but in the fifth test 40,000 watches are in force at once, and the scan costs about a billion operations.
- Forgetting equal ends. Watches that ended at the same time are printed by region number; pairs (end, region) in the heap give this order for free.