#1539. 「CodePlus #7」蚂蚁

「CodePlus #7」蚂蚁

题目描述

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

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

输入格式

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

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

输入的第三行包含 NN 个整数,第 ii 个数 did_i 若为 11 则表示第 ii 只蚂蚁一开始朝向西侧,为 00 则表示朝向东侧。

输出格式

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

样例

3 6
1 3 5
1 1 0
5 5 3

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

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

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

数据范围与提示

子任务 111717 分)

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

子任务 221919 分)

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

子任务 332727 分)

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

子任务 443737 分)

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