#522. 「LibreOJ β Round #3」绯色 IOI(危机)

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

题目描述

IOI 的比赛开始了。Jsp 和 Rlc 坐在一个角落,这时他们听到了一个异样的声音 ……

黑恶势力登场

接着他们发现自己收到了一封电子邮件:

我们在考场上放置了 NN 个炸弹。如果建立一个直线坐标系(数轴)的话,第 ii 个炸弹的坐标是 XiX_i,爆炸半径是 RiR_i,当一个炸弹爆炸时,如果另一个炸弹所在位置 XjX_j 满足:

XiRiXjXi+Ri X_i-R_i\leq X_j\leq X_i+R_i

那么,炸弹 jj 也会被引爆。

iijj 满足上述关系式,称 ii 能直接引爆 jj。若 ii 不能直接引爆 jj,但引爆 ii 会导致 jj 爆炸,则称 ii 能间接引爆 jj

我可以告诉你们,这些炸弹满足一个性质:若引爆炸弹 AA 会直接或间接地引爆炸弹 BB,则引爆炸弹 BB 一定不会直接或间接地引爆炸弹 AA

有能耐就拆掉炸弹吧!记住,如果其它选手有所动作的话,后果你们应该知道!

吃惊的 Jsp 和 Rlc 开始了调(报)查(警)。之后,这些话被证实了。并且两人还发现了另一个性质:

定义炸弹 AABB 的“引爆距离”(用 d(A,B)d(A,B) 表示)为最长的满足以下条件的序列 a1,a2,...,ana_1,a_2,...,a_n 的长度:

  1. aia_i 互不相同,且为 [1,N][1,N] 中的整数;
  2. aia_i直接引爆 ai+1a_{i+1}
  3. a1=A,an=Ba_1=A,a_n=B

那么这个性质可以表述为:若 d(A,B)=3d(A,B)=3AA 一定能直接引爆 BB

经过进一步研究,Rlc 发现最为安全的方法是这样:首先选出若干个关键炸弹安装监测器,然后慢慢拆除。

因为炸弹的某些特性,安装监测器的炸弹必须组成一个有序序列 a1,a2,...,ana_1,a_2,...,a_n,且满足:

  1. aia_i 互不相同,且为 [1,N][1,N] 中的整数。
  2. aia_i直接或间接引爆 ai+1a_{i+1}

Rlc 设计了一个衡量监测器安装方案的安全程度的方法:

首先可以测出每个炸弹的特征值 viv_i
那么监测器安装方案的安全程度为:i=1n1F(vai,vai+1)\sum_{i=1}^{n-1}F(v_{a_i},v_{a_{i+1}}),其中 F(x,y)=(xy+xy)mod998244353F(x,y)=(x\oplus y+xy)\bmod 998244353\oplus 表示二进制按位异或,本题中按位异或的优先级高于乘法和加法)。

现在她想知道,对于 [1,N][1,N] 中的每个整数 ii,如果她安装监测器的最后一个炸弹是 ii(即 an=ia_n=i),安全程度最大是多少。

请特别注意,题面中大写的 NN 表示炸弹总数,小写 nn 表示上下文中的序列长度,请勿混淆。

输入格式

第一行一个整数 NN 表示炸弹个数。
第二行 NN 个整数 X1,X2,...,XNX_1,X_2,...,X_N,表示炸弹的坐标。
第三行 NN 个整数 R1,R2,...,RNR_1,R_2,...,R_N,表示炸弹的爆炸半径。
第四行 NN 个整数 v1,v2,...,vNv_1,v_2,...,v_N,表示炸弹的特征值。

输出格式

输出 NN 行,每行一个整数,第 ii 行表示拆除的最后一个炸弹是 ii 时的最大安全程度。

样例

样例输入

6
-3 -2 0 2 3 4
0 1 4 1 0 1
4 1 3 4 2 0

样例输出

19
5
0
19
33
3

样例解释

11 结尾的最优监测器安装序列:3,13,1
22 结尾的最优监测器安装序列:3,23,2
33 结尾的最优监测器安装序列:33
44 结尾的最优监测器安装序列:3,43,4
55 结尾的最优监测器安装序列:3,4,53,4,5
66 结尾的最优监测器安装序列:3,63,6

数据范围与提示

对于所有数据,1N3×105,0vi<998244353,0Ri1018,Xi10181\leq N\leq 3\times 10^5,0\leq v_i<998244353,0\leq R_i\leq 10^{18},|X_i|\leq 10^{18}

请特别注意,题面中大写的 NN 表示炸弹总数,小写 nn 表示上下文中的序列长度,请勿混淆。

Subtask # 分值 NN 的限制 vv 的限制 RR 的限制
1 1010 1N101 \leq N \leq 10
2 1010 1N3001 \leq N \leq 300
3 1010 1N30001 \leq N \leq 3000
4 1010 1N3×1051 \leq N \leq 3\times 10^5 vi=1v_i=1
5 1515 vi{0,1}v_i\in\{0,1\}
6 1515 Ri104R_i\leq 10^4
7 3030