Queue in the Train
Contest: Codeforces Round 594 (Div. 1)
Difficulty rating: 2300
Tags: data structures, greedy, implementation

There are $$$n$$$ seats in the train's car and there is exactly one passenger occupying every seat. The seats are numbered from $$$1$$$ to $$$n$$$ from left to right. The trip is long, so each passenger will become hungry at some moment of time and will go to take boiled water for his noodles. The person at seat $$$i$$$ ($$$1 \leq i \leq n$$$) will decide to go for boiled water at minute $$$t_i$$$.

Tank with a boiled water is located to the left of the $$$1$$$-st seat. In case too many passengers will go for boiled water simultaneously, they will form a queue, since there can be only one passenger using the tank at each particular moment of time. Each passenger uses the tank for exactly $$$p$$$ minutes. We assume that the time it takes passengers to go from their seat to the tank is negligibly small.

Nobody likes to stand in a queue. So when the passenger occupying the $$$i$$$-th seat wants to go for a boiled water, he will first take a look on all seats from $$$1$$$ to $$$i - 1$$$. In case at least one of those seats is empty, he assumes that those people are standing in a queue right now, so he would be better seating for the time being. However, at the very first moment he observes that all seats with numbers smaller than $$$i$$$ are busy, he will go to the tank.

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them (that is, seating on the seat with smallest number) will go to the tank, while all others will wait for the next moment.

Your goal is to find for each passenger, when he will receive the boiled water for his noodles.

Input format:
The first line contains integers $$$n$$$ and $$$p$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1 \leq p \leq 10^9$$$) — the number of people and the amount of time one person uses the tank.

The second line contains $$$n$$$ integers $$$t_1, t_2, \dots, t_n$$$ ($$$0 \leq t_i \leq 10^9$$$) — the moments when the corresponding passenger will go for the boiled water.

Output format:
Print $$$n$$$ integers, where $$$i$$$-th of them is the time moment the passenger on $$$i$$$-th seat will receive his boiled water.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
Consider the example.

At the $$$0$$$-th minute there were two passengers willing to go for a water, passenger $$$1$$$ and $$$5$$$, so the first passenger has gone first, and returned at the $$$314$$$-th minute. At this moment the passenger $$$2$$$ was already willing to go for the water, so the passenger $$$2$$$ has gone next, and so on. In the end, $$$5$$$-th passenger was last to receive the boiled water.

Example input:
5 314
0 310 942 628 0

Example output:
314 628 1256 942 1570

Editorial:
The problem can be solved easily with an abstraction of "events". Let's define an "event" as a tuple of variables $$$(time, type, index)$$$, where $$$index$$$ is the index of the passenger $$$(1 \leq index \leq n)$$$, $$$time$$$ is the time when the event will happen, $$$type$$$ is either $$$0$$$ (the passenger exits the queue) or $$$1$$$ (the passenger wants to enter the queue).
To simulate the activity described in the problem it's necessary to handle events in sorted order. At the start there are $$$n$$$ events $$$(t_i, 1, i)$$$, where $$$1 \leq i \leq n$$$. While there are any unprocessed events, we take the "smallest" event and process it. Event $$$(a, b, c)$$$ is "smaller" than event $$$(d, e, f)$$$ either if $$$(a < d)$$$ or $$$(a = d\ and\ b < e)$$$ or $$$(a = d\ and\ b = e\ and\ c < f)$$$.
Let's define a few sets: $$$want$$$ (the set of passengers who want to enter the queue), $$$in\_queue$$$ (the set of passengers who are in the queue); and a few integer variables: $$$queue\_time$$$ (the time when the queue becomes empty, to help calculate the time when a new passenger will exit the queue if he enters now), $$$cur\_time$$$ (time of the last processed event).
Suppose that we're processing an event. If the $$$type$$$ of the event is $$$1$$$, then we add $$$index$$$ to $$$want$$$, otherwise we remove $$$index$$$ from $$$in\_queue$$$. After processing an event we ought to check if there is a passenger who can enter the queue. Let $$$x$$$ be the smallest element of $$$want$$$, and if $$$in\_queue$$$ either is empty or $$$x$$$ is smaller than the smallest element of $$$in\_queue$$$, then $$$x$$$ immediately enters the queue, therefore creating a new event $$$(max(cur\_time, queue\_time) + p, 0, x)$$$.
The complexity of the solution is $$$O(n log n)$$$, because we need to use sorted data structures (for example, std::set of std::priority_queue).