Mission control operates a relay that schedules deep-space beacons to transmit a payload value after a delay, but any pending beacon can still be called off before its transmission fires. You are given the full timestamped ledger of commands mission control issued, in the exact chronological order they were issued, and must determine which beacons actually transmit and in what order. Each SCHEDULE command arms a beacon with a unique id: it is scheduled at the moment the command is issued and will transmit its payload after the stated delay elapses, unless it is cancelled first. Each CANCEL command names a previously-scheduled beacon id; the cancellation succeeds — permanently suppressing that beacon's transmission — only if it is issued strictly before the beacon's scheduled transmission moment. A cancellation issued at or after that moment has no effect (the transmission is treated as already underway).
Line 1: an integer n — the number of commands. Each of the next n lines is one of:
t SCHEDULE id delay payload — at time t, mission control arms beacon id, which will transmit payload at time t + delay unless cancelled first.t CANCEL id — at time t, mission control attempts to cancel beacon id.The lines are given in non-decreasing order of t (the order the commands were actually issued).
Print one line id payload for every beacon that ends up transmitting, ordered by transmission time ascending; break ties (equal transmission time) by id ascending, numerically. Print nothing if no beacon transmits.
id that appears in a SCHEDULE command satisfies 1 <= id <= 10^9, and is used in at most one SCHEDULE command in the whole input.id that appears in a CANCEL command was used in an earlier SCHEDULE command.Example 1
Input
3 0 SCHEDULE 1 5 100 2 CANCEL 1 3 SCHEDULE 2 1 200
Expected
2 200
Explanation
Beacon 1 is armed at t=0 with delay 5, so it would transmit at t=5. The cancel at t=2 is strictly before t=5, so it succeeds and beacon 1 never transmits. Beacon 2 is armed at t=3 with delay 1, transmitting at t=4 with payload 200, and it is never cancelled. Only one transmission happens, so the output is a single line: "2 200".
Example 2
Input
4 0 SCHEDULE 10 5 111 0 SCHEDULE 3 5 222 1 SCHEDULE 7 3 333 5 CANCEL 10
Expected
7 333 3 222 10 111
Explanation
Beacon 10 (armed t=0, delay 5) and beacon 3 (armed t=0, delay 5) both transmit at t=5. Beacon 7 (armed t=1, delay 3) transmits at t=4. The cancel for beacon 10 arrives at t=5, which is not strictly before its own transmission time of 5, so the cancel has no effect and beacon 10 still transmits. Sorted by transmission time then id: beacon 7 (t=4) first, then beacons 3 and 10 (both t=5, tie broken by the smaller id 3 before 10). Output: "7 333" then "3 222" then "10 111".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →