← 返回题目列表

Codeforces · 1039/A

A. 时间表

中文机器翻译题面 查看原题

有两个巴士站,分别标记为 A 和 B,每天有 $$$n$$$ 巴士从 A 开往 B。从 A 到 B 的最短路径需要 $$$t$$$ 时间单位,但某些公共汽车可能需要更长的路径。此外,巴士在路线上可以互相超车。

在每个车站,人们都可以找到公交车到达该车站的时间时刻的排序列表。对于 A 站,我们将此列表表示为 $$$a_1 < a_2 < \ldots < a_n$$$,对于 B 站,我们将其表示为 $$$b_1 < b_2 < \ldots < b_n$$$。巴士总是根据时刻表从 A 出发并到达 B,但巴士到达的顺序可能有所不同。如果每辆公交车到达时间比出发晚至少 $$$t$$$ 个时间单位,我们就称到达顺序有效。

众所周知,要使订单有效,从 $$$a_i$$$ 出发的巴士最迟可能到达的时间是 $$$b_{x_i}$$$,即时间表中的第 $$$x_i$$$。换句话说,对于每个$$$i$$$,存在这样一个有效的到达顺序:第$$$i$$$出发的公共汽车到达第$$$x_i$$$(并且所有其他公共汽车可以任意到达),但是不存在第$$$i$$$出发的公共汽车到达第$$$(x_i + 1)$$$-th的有效到达顺序。

正式地,如果 $$$b_{p_i} \ge a_i + t$$$ 对于所有 $$$i$$$ 来说,我们称排列 $$$p_1, p_2, \ldots, p_n$$$ 有效。那么 $$$x_i$$$ 就是所有有效排列中 $$$p_i$$$ 的最大值。

您会得到序列 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$x_1, x_2, \ldots, x_n$$$,但没有到达时间表。找出 B 站 $$$b_1, b_2, \ldots, b_n$$$ 任何合适的时间表,或确定没有这样的时间表。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$t$$$ ($$$1 \leq n \leq 200\,000$$$, $$$1 \leq t \leq 10^{18}$$$) - 时间表中的公交车数量以及从站点 A 到站点 B 的最短可能行驶时间。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_1 < a_2 < \ldots < a_n \leq 10^{18}$$$),定义公交车离开 A 站的时刻。

第三行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq n$$$),其中第 $$$i$$$ 代表从 A 站出发的第 $$$i$$$ 辆公交车可以到达 B 站的最大可能时刻表位置。

输出

如果存在解决方案,请在输出的第一行打印“Yes”(不带引号)。

在第二行中打印 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_1 < b_2 < \ldots < b_n \leq 3 \cdot 10^{18}$$$)。我们可以证明,如果存在任何解,则存在满足 $$$b_i$$$ 的此类约束的解。如果有多个有效答案,您可以打印其中任何一个。

如果没有有效的时间表,则在输出的唯一行中打印“No”(不带引号)。

示例

输入 #1

3 10
4 6 8
2 2 3

输出 #1

Yes
16 17 21

输入 #2

2 1
1 2
2 1

输出 #2

No

注意

考虑第一个示例和输出中的时间表 $$$b_1, b_2, \ldots, b_n$$$。

要获得 $$$x_1 = 2$$$,公交车可以按 $$$(2, 1, 3)$$$ 的顺序到达。要获得 $$$x_2 = 2$$$ 和 $$$x_3 = 3$$$,公共汽车可以按 $$$(1, 2, 3)$$$ 的顺序到达。 $$$x_1$$$ 不是 $$$3$$$,因为排列 $$$(3, 1, 2)$$$ 和 $$$(3, 2, 1)$$$(其中 $$$1$$$-st 巴士到达 $$$3$$$-rd)无效(sube 巴士到达太早),由于类似的原因,$$$x_2$$$ 不是 $$$3$$$。