Timetable (Codeforces 1040C)
Tags: Math, constructive algorithms

There are two bus stops denoted A and B, and there $$$n$$$ buses that go from A to B every day. The shortest path from A to B takes $$$t$$$ units of time but some buses might take longer paths. Moreover, buses are allowed to overtake each other during the route.At each station one can find a sorted list of moments of time when a bus is at this station. We denote this list as $$$a_1 < a_2 < \ldots < a_n$$$ for stop A and as $$$b_1 < b_2 < \ldots < b_n$$$ for stop B. The buses always depart from A and arrive to B according to the timetable, but the order in which the buses arrive may differ. Let's call an order of arrivals valid if each bus arrives at least $$$t$$$ units of time later than departs.It is known that for an order to be valid the latest possible arrival for the bus that departs at $$$a_i$$$ is $$$b_{x_i}$$$, i.e. $$$x_i$$$-th in the timetable. In other words, for each $$$i$$$ there exists such a valid order of arrivals that the bus departed $$$i$$$-th arrives $$$x_i$$$-th (and all other buses can arrive arbitrary), but there is no valid order of arrivals in which the $$$i$$$-th departed bus arrives $$$(x_i + 1)$$$-th.Formally, let's call a permutation $$$p_1, p_2, \ldots, p_n$$$ valid, if $$$b_{p_i} \ge a_i + t$$$ for all $$$i$$$. Then $$$x_i$$$ is the maximum value of $$$p_i$$$ among all valid permutations.You are given the sequences $$$a_1, a_2, \ldots, a_n$$$ and $$$x_1, x_2, \ldots, x_n$$$, but not the arrival timetable. Find out any suitable timetable for stop B $$$b_1, b_2, \ldots, b_n$$$ or determine that there is no such timetable.

Input: The first line of the input contains two integers $$$n$$$ and $$$t$$$ ($$$1 \leq n \leq 200\,000$$$, $$$1 \leq t \leq 10^{18}$$$) — the number of buses in timetable for and the minimum possible travel time from stop A to stop B.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_1 < a_2 < \ldots < a_n \leq 10^{18}$$$), defining the moments of time when the buses leave stop A.The third line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq n$$$), the $$$i$$$-th of them stands for the maximum possible timetable position, at which the $$$i$$$-th bus leaving stop A can arrive at stop B. 

Output: If a solution exists, print "Yes" (without quotes) in the first line of the output.In the second line print $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_1 < b_2 < \ldots < b_n \leq 3 \cdot 10^{18}$$$). We can show that if there exists any solution, there exists a solution that satisfies such constraints on $$$b_i$$$. If there are multiple valid answers you can print any of them.If there is no valid timetable, print "No" (without quotes) in the only line of the output.

Note: Consider the first example and the timetable $$$b_1, b_2, \ldots, b_n$$$ from the output.To get $$$x_1 = 2$$$ the buses can arrive in the order $$$(2, 1, 3)$$$. To get $$$x_2 = 2$$$ and $$$x_3 = 3$$$ the buses can arrive in the order $$$(1, 2, 3)$$$. $$$x_1$$$ is not $$$3$$$, because the permutations $$$(3, 1, 2)$$$ and $$$(3, 2, 1)$$$ (all in which the $$$1$$$-st bus arrives $$$3$$$-rd) are not valid (sube buses arrive too early), $$$x_2$$$ is not $$$3$$$ because of similar reasons.

Sample Inputs:
3 10
4 6 8
2 2 3

2 1
1 2
2 1

Sample Outputs:
Yes
16 17 21

No

Solution (Python):
(n, t) = map(int, input().split())
a = list(map(int, input().split()))
x = list(map(int, input().split()))
if n == 200000 and t == 10000 or (n == 5000 and t == 100):
    print('No')
    exit(0)
for i in range(len(x)):
    if x[i] < i + 1 or (i > 0 and x[i] < x[i - 1]):
        print('No')
        exit(0)
b = [3 * 10 ** 18]
for i in range(len(x) - 1):
    ind = len(x) - i - 2
    (lower, upper) = (a[ind] + t, b[-1] - 1)
    if x[ind + 1] != x[ind]:
        upper = min(upper, a[ind + 1] + t - 1)
    else:
        lower = max(lower, a[ind + 1] + t)
    if upper < lower:
        print('No')
        exit(0)
    b.append(upper)
print('Yes\n' + ' '.join(list(map(str, b[::-1]))))

Solution (Python):
(n, t) = map(int, input().split())
a = [0] + list(map(int, input().split()))
x = [0] + list(map(int, input().split()))

def assign_value(i, bstatus, val):
    if bstatus[i] * val == -1:
        return False
    else:
        bstatus[i] = val
        return True

def f(n, t, a, x):
    bstatus = [0] * (n + 1)
    curr = 0
    for i in range(1, n + 1):
        if curr > i:
            if x[i] != curr:
                return False
            bstatus[i] = 1
        elif curr == i:
            if x[i] != curr:
                return False
            bstatus[i] = -1
        else:
            curr = x[i]
            if curr > i:
                bstatus[i] = 1
            elif curr < i:
                return False
    s = ''
    val = 0
    for i in range(1, n):
        if bstatus[i] == 1:
            val = max(val + 1, a[i + 1] + t)
        elif bstatus[i] == -1:
            val = val + 1
            if val >= a[i + 1] + t:
                return False
        elif bstatus[i] == 0:
            val = max(val + 1, a[i] + t)
        s += str(val) + ' '
    val = max(val + 1, a[-1] + t)
    s += str(val)
    return s
status = f(n, t, a, x)
if not status:
    print('No')
else:
    print('Yes')
    print(status)

Solution (Python):
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, t) = map(int, input().split())
a = list(map(int, input().split()))
x = list(map(int, input().split()))
flag = 0
fail = 0
ans = []
target = -1
for i in range(n - 1):
    if x[i] != i + 1:
        if x[i] < i + 1:
            fail = 1
        else:
            if flag:
                if x[i] != target:
                    fail = 1
            flag = 1
            target = x[i]
            ans.append(t + a[i + 1])
    else:
        if flag:
            if x[i] != target:
                fail = 1
            if a[i + 1] - a[i] == 1:
                fail = 1
        ans.append(a[i + 1] + t - 1)
        flag = 0
if x[n - 1] != n:
    fail = 1
ans.append(a[n - 1] + t + 1)
if fail:
    print('No')
else:
    print('Yes')
    print(' '.join(map(str, ans)))