#6721. 「CodePlus #7」蚂蚁

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

在东西排布的两棵树之间悬挂着一条长为 L 的细绳,有 N 只蚂蚁在这条绳上。这些蚂蚁希望通过绳子爬到任何一棵树上,但这条绳太细了,导致两只蚂蚁不能并排爬行,也不能交错而过。

它们想到了一个方法:每只蚂蚁都以每单位时间移动一个单位距离的速度不断向前爬,当迎面碰到另一只蚂蚁时,两只蚂蚁都将立即掉头并继续向前爬。现在,蚂蚁们想知道自己是否能爬下绳子,如果能,它们还希望知道自己爬下绳子所花的时间。为了方便,我们按初始时位置从东到西的顺序对蚂蚁从 1 开始编号。

输入格式

输入的第一行包含两个正整数 N, L ,保证 N\le 10^5, L\le 10^9 ,且 N<L

输入的第二行包含 N 个正整数,第 i 个数 p_i 表示第 i 只蚂蚁到东侧树木的距离,保证 p_i i 增大严格递增,且 0<p_i<L

输入的第三行包含 N 个整数,第 i 个数 d_i 若为 1 则表示第 i 只蚂蚁一开始朝向西侧,为 0 则表示朝向东侧。

输出格式

输出仅一行,包含 N 个数,第 i 个数表示第 i 只蚂蚁爬下绳子所花时间,四舍五入保留到整数。若第 i 只蚂蚁无法爬下绳子,则输出的第 i 个数为 -1

样例

样例输入

3 6
1 3 5
1 1 0

样例输出

5 5 3

样例解释

第三只蚂蚁在爬行 1 个单位时间后遇见第二只蚂蚁并掉头,再爬行 2 个单位时间到西侧树木;

第二只蚂蚁在爬行 1 个单位时间后遇见第三只蚂蚁并掉头,再爬行 1 个单位时间后遇见第一只蚂蚁并掉头,再爬行 3 个单位时间到西侧树木;

第一只蚂蚁在爬行 2 个单位时间后遇见第二只蚂蚁并掉头,再爬行 3 个单位时间到东侧树木。

数据范围与提示

子任务 1 17 分)

  • 1\le N\le 10, L\le 10^5

子任务 2 19 分)

  • 1\le N\le 100, L\le 10^9

子任务 3 27 分)

  • 1\le N\le 5000, L\le 10^9

子任务 4 37 分)

  • 1\le N\le 10^5, L\le 10^9