Queue in the Train (Codeforces 1239C)
Tags: Greedy, data structures

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: 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: Print $$$n$$$ integers, where $$$i$$$-th of them is the time moment the passenger on $$$i$$$-th seat will receive his boiled water.

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.

Sample Inputs:
5 314
0 310 942 628 0

Sample Outputs:
314 628 1256 942 1570

Solution (Python):
import heapq
(n, p) = map(int, input().split(' '))
ti = map(int, input().split(' '))
pq = []
wait = []
for (i, v) in enumerate(ti):
    heapq.heappush(pq, [v, i])
seq = []
now = 0
ans = [0] * n
while pq:
    (v, i) = heapq.heappop(pq)
    now = v
    heapq.heappush(wait, [i, v])
    while wait:
        (ni, nv) = heapq.heappop(wait)
        i = ni
        now = now + p
        ans[i] = now
        while pq and pq[0][0] <= now:
            (nv, ni) = heapq.heappop(pq)
            if ni < i:
                now = now + p
                i = ni
                ans[i] = now
            else:
                heapq.heappush(wait, [ni, nv])
print(' '.join(map(str, ans)))

Solution (Python):
import heapq
(n, p) = map(int, input().split(' '))
ti = map(int, input().split(' '))
pq = []
wait = []
for (i, v) in enumerate(ti):
    heapq.heappush(pq, [v, i])
seq = []
now = 0
ans = [0] * n
while pq:
    (v, i) = heapq.heappop(pq)
    now = v
    heapq.heappush(wait, [i, v])
    while wait:
        (ni, nv) = heapq.heappop(wait)
        i = ni
        now = now + p
        ans[i] = now
        while pq and pq[0][0] <= now:
            (nv, ni) = heapq.heappop(pq)
            if ni < i:
                now = now + p
                i = ni
                ans[i] = now
            else:
                heapq.heappush(wait, [ni, nv])
print(' '.join(map(str, ans)))

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

def main():
    (n, k) = MII()
    nums = LII()
    ans = [-1] * n
    hpq = [nums[i] * n + i for i in range(n)]
    heapify(hpq)
    cur = 0
    waits = []
    while hpq:
        (v, i) = divmod(heappop(hpq), n)
        cur = v
        heappush(waits, i)
        while waits:
            i = heappop(waits)
            cur += k
            ans[i] = cur
            while hpq and hpq[0] // n <= cur:
                (v, ni) = divmod(heappop(hpq), n)
                if ni < i:
                    cur += k
                    i = ni
                    ans[i] = cur
                else:
                    heappush(waits, ni)
    print(*ans)
    return
t = 1
for _ in range(t):
    main()