2162. A Break After Every b-th Customer
One clerk serves n customers strictly in the order given, with arrival times
non-decreasing. Customer i needs d[i] units of service. After finishing
every b-th customer, counting from the first, the clerk takes a break of
exactly k units and is unavailable for that whole stretch.
available = 0
for i = 0, 1, ..., n-1:
start = max(arrival[i], available)
depart[i] = start + d[i]
available = depart[i]
if (i + 1) is a multiple of b:
available = available + k
Print the n departure times, one per line.
``` n = 3, b = 1, k = 2, customers (0,5) (0,3) (0,4)
customer 0: 0 to 5, then a break to 7 customer 1: 7 to 10, then a break to 12 customer 2: 12 to 16 -> 5 10 16 ```
``` n = 3, b = 2, k = 2, customers (0,5) (0,3) (0,4)
customer 0: 0 to 5, no break, since 1 is not a multiple of 2 customer 1: 5 to 8, then a break to 10 customer 2: 10 to 14 -> 5 8 14 ```
## What most people try first
Counting the break from the start of a service rather than its end, or counting
services from zero so that the break lands after customers 0, b, 2b and so
on. The second is an off-by-one that is invisible when b is 1, because then
the clerk breaks after every customer either way. The two worked examples above
differ only in b, which is what makes the boundary visible.
The other common error is adding the break to the customer's departure time.
The break happens after the customer has left, so it shifts the next start and
never the current departure. Printing start + d[i] + k would make the first
example read 7, 12, 16.
## Why the recurrence is enough
The clerk never chooses anything, so there is nothing to search. The only state
is the moment the clerk is next available, and each customer reads it, writes
it, and possibly pushes it forward by k. Each step depends on exactly one
earlier value, so a single left to right pass computes all of them, and no
second pass can change an answer already printed.
The max is what makes an idle clerk work. If the next customer arrives after
the clerk is available, the clerk simply waits, and available plays no part.
If they arrive while the clerk is busy or on a break, they start the moment it
ends.
A break is taken after the b-th, 2b-th, 3b-th service and so on, which
means a final break can be taken after the last customer. It changes nothing
that is printed, so it is harmless, but a solution that skips it must skip it
for the right reason and not by using it as a condition.
## Overflow
With n up to 10^5 and both a service and a break up to 10^9, the
available time can advance by 2 * 10^9 per customer and reach roughly
2 * 10^14. That is far outside a signed 32 bit integer, whose top is
2147483647. Every time here must be 64 bit. The declared test with b = 1,
a break of 10^9 and three services of 10^9 ends at 5 * 10^9, which a 32
bit build prints as a wrapped negative value.
## Cost
O(n) time and O(1) extra memory beyond the output.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ b ≤ 10^9` - `0 ≤ k ≤ 10^9` - `0 ≤ arrival ≤ 10^9`, non-decreasing over the input - `1 ≤ duration ≤ 10^9` - customers are served strictly in the order given - the break follows the completion of the b-th, 2b-th, 3b-th service and so on
Input
The first line contains three integers n, b and k: the number of customers, how many services the clerk completes between breaks, and the length of one break.
Each of the next n lines contains two integers, the arrival time and the service duration of one customer, in non-decreasing order of arrival time.
Output
Print n lines. Line i holds one integer, the time at which the service of customer i ended.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.