2160. The Clerk Who Serves the Newest Arrival

One clerk serves n customers. Customer i arrives at a[i] and needs d[i] units of service. Arrival times may appear in any order in the input and two customers may share one.

This clerk works through the pile from the top:

the clerk is free at time 0, and again at the end of each service. when the clerk becomes free: consider every customer not yet served whose arrival is <= now. if none, the clock jumps to the smallest arrival among the unserved. serve the one who arrived LATEST. Ties go to the LARGER input index. no service is ever interrupted.

Print, in service order, the index of each customer and the moment their service ended.

``` n = 3, customers (0,5) (1,3) (2,4)

only customer 0 is present at time 0, so it is served, 0 to 5. at time 5 both 1 and 2 are waiting; customer 2 arrived later, so it goes next, 5 to 9, and customer 1 last, 9 to 12. -> 0 5 2 9 1 12 ```

``` n = 3, customers (0,2) (0,2) (0,2)

all three arrive together, so the arrival time ties and the larger index wins: 2, then 1, then 0. -> 2 2 1 4 0 6 ```

## What most people try first

Sorting by arrival time descending and serving that order. It is wrong for the same reason the opposite mistake is wrong on a priority queue: the rule picks the latest arrival among those who are PRESENT, and a customer who has not arrived yet is not present. In the first worked example, customer 2 arrives latest of all three, and yet customer 0 is served first, because at time 0 it was the only one there.

The direct reading is a selection loop:

repeat n times: best = the unserved customer with a[i] <= clock maximising (a[i], i) if there is none, clock = min arrival over unserved, then choose again clock += d[best]; report (best, clock)

## Why this is a stack, and why that matters

Push the customers onto a stack in order of (arrival, index) as the clock passes their arrival times, and the rule becomes "pop the top". The latest arrival with the largest index on a tie is exactly the most recently pushed item, so last in, first out is not an analogy here, it is the definition. That is also the second implementation used to verify every declared output, written differently on purpose so that a mistake in the scanning version cannot be mirrored in the checker.

The consequence worth noticing is starvation: an early customer can wait arbitrarily long, and in the second worked example customer 0 is served last despite arriving first. Nothing in the rule prevents that, and the problem does not ask you to fix it.

## The clock jump is necessary

If nobody is present the clerk is idle, no service is running, and no arrival can happen before the smallest unserved arrival time. So nothing can change between now and then and the clock may move straight there. Stepping it one unit at a time is correct and far too slow, since arrival times reach 10^9.

## Overflow

Up to 2000 services of 10^9 each, starting from an arrival of up to 10^9, put the clock as high as about 2 * 10^12. A signed 32 bit integer stops at 2147483647, so the clock must be 64 bit.

## Cost

O(n^2) with the scanning version above, or O(n log n) with the stack and a sort, and O(n) memory either way.

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ arrival ≤ 10^9`, in any order in the input - `1 ≤ duration ≤ 10^9` - among the customers present, the latest arrival is served, and ties go to the larger index - a service once started runs to completion