2156. The Lowest Numbered Free Till

A shop has c tills, numbered 0 to c - 1. n customers arrive, given in non-decreasing order of arrival time. Customer i needs d[i] units of service once a till starts on them.

The discipline is fixed and you are not asked to improve it:

1. customers are served in the order given, strictly. Customer i+1 cannot start before customer i has started. 2. customer i starts at the later of their own arrival time and the earliest moment any till is free. 3. if more than one till is free at that moment, the LOWEST numbered one is used.

For every customer, print the till that served them and the moment their service ended.

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

one till, so the services form a chain: customer 0 starts at 0 and ends at 5 customer 1 arrived at 1 but the till is busy until 5, so 5 to 8 customer 2 arrived at 2, so 8 to 12 -> 0 5 0 8 0 12 ```

``` n = 3, c = 2, customers (10,1) (10,1) (10,1)

tills 0 and 1 are both free at time 10. The first customer takes till 0 because it is the lower number, the second takes till 1, and the third waits for the earliest free moment, which is 11 on both tills, so it takes till 0 again. -> 0 11 1 11 0 12 ```

## What most people try first

A loop over time, one unit at a time, freeing tills and starting whoever is at the front. That is a faithful reading of the rules and it is too slow here: arrival times reach 10^9 and a single service can be 10^9 units long, so the clock would have to take 10^9 steps that change nothing.

The useful observation is that you never need the clock at all. Keep one number per till, free[j], the moment till j next becomes available, and process customers in the order given:

earliest = min over j of free[j] start = max(arrival[i], earliest) till = the smallest j with free[j] <= start free[till] = start + d[i]

## Why the smallest such j always exists

start is at least earliest, and earliest is free[j] for at least one till j, so that till satisfies free[j] <= start. The scan therefore never falls off the end, and taking the first j it finds gives exactly the lowest numbered free till, which is the tie-break the statement names.

The reason it is correct to serve in the given order at all is that arrivals are non-decreasing. If customer i + 1 could start before customer i, then at that earlier moment a till was free and customer i had already arrived, since arrival[i] <= arrival[i+1], so customer i would have taken it.

## The boundary that breaks a careless implementation

Writing free[j] < start instead of free[j] <= start loses the common case where a till frees at the exact instant the next customer is ready. On the second worked example that turns 0 12 into no till being found at all.

Two customers may share an arrival time, and c may exceed n, in which case the later tills are never touched.

## Overflow

With n up to 10^5 and each service up to 10^9, a single till can be busy until roughly 10^14, which is far outside a signed 32 bit integer. Hold every time in a 64 bit type. The declared test with three billion-unit services on one till ends at 3 * 10^9, which already does not fit in 32 bits, and a 32 bit build prints a negative number for it.

## Cost

O(n c) time for the two scans per customer, and O(c) memory.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ c ≤ 50` - `0 ≤ arrival ≤ 10^9`, non-decreasing over the input - `1 ≤ duration ≤ 10^9` - customers start in the order given - ties between free tills go to the lowest numbered till