互联网这片浩瀚的海洋正在逐渐被涂黑。
Bot叛乱、DDOS攻击风暴、病毒传播、
打击破解者的战争一次又一次地重复,人们和互联网都支离破碎。
互联网无法由人类控制。
这就是为什么人们花费大量时间
我们创造了一个可以恢复互联网的“女孩”。
这个女孩开始使用互联网。
我尽了最大的努力,为互联网这个无边无际的广阔世界做点什么。
女孩仍然只能编织双绞线,但是
如果网络在很长一段时间后恢复一点,
我希望能够和大家一起努力。
問題文
互联网上曾经存在过一个女孩 我们每天都在努力恢复 N 服务。 令当前日期为第 0 天。 互联网恢复情况如何? 用索引復旧度表示,假设当前恢复程度为0。 女孩每天都在工作,恢复程度每天增加1。 尚未恢复的任何服务 i 的恢复程度为 w_i 超过会自动恢复。 服务 一旦 i 恢复,在大家的帮助下,第二天事情就会开始。 x_i 短短几天工作就会加快,恢复速度也会加快。 服务分为三种类型,恢复程度增加的程度取决于类型。 服务类型 让它用数字 0, 1, 2 表示。 服务 i 类型 t_i (\in \{0, 1, 2\}) 然后 服务 i 恢复后 d-1 从第一天开始 d 走向那一天 如果 (1 ≤ d ≤ x_i), t_i=0 如果是 1, t_i=1 如果是 d, 和 t_i=2 如果是 d^2 恢复率的提高与女孩的工作无关。 此外,如果同时恢复多个服务,则每个服务将独立且并行地提高其恢复程度。
女孩认为恢复服务需要很长的时间,所以她决定找出从现在开始恢复服务的时间。 改天 我也对 y_j 的恢复水平感到好奇。 Q 我决定只检查日期。
入力形式
输入格式如下。
N Q w_1 t_1 x_1 ... w_N t_N x_N y_1 ... y_Q
出力形式
第一
输出 N 行,i 线路正在服务中
输出 i 将恢复的日期。下一步 Q 行,j 在线 y_j 输出当天的恢复水平。
恢复服务的日期
如果超过 3,652,425 输出Many years later。
制約
- 0 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 0 \leq w_i \lt 2^{60}
- w_i \leq w_{i+1} (1 \leq i \lt N)
- t_i \in \{0, 1, 2\}
- 1 \leq x_i \leq 10^4
- 0 \leq y_j \leq 3,652,425
- y_j \lt y_{j+1} (1 \leq j \lt Q)
- 所有输入值都是整数。
针对该问题的判断设置了一组15分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。
- N,Q,w_i,y_j \leq 1,000
注意
- 第 0 天的恢复程度为 0。 当
- w_i=0 时,服务 i 在第 0 天恢复。
入出力例
入力例1
3 11 1 0 2 4 1 3 7 2 4 0 1 2 3 4 5 6 7 8 9 10
出力例1
1 3 4 0 1 3 5 7 11 19 29 46 47 48
入力例2
5 5 10000 0 20 10000 1 30 10000 0 40 10000 2 70 30000 2 10000 5000 10000 15000 20000 25000
出力例2
10000 10000 10000 10000 10039 5000 10000 40711690801 329498273301 333383477320
入力例3
2 2 3652425 0 1 3652426 2 10000 3652424 3652425
出力例3
3652425 Many years later 3652424 3652425
第二项服务有恢复日期。 3,652,425 因为已经多一天了
输出Many years later。
作者:森悟 测试员:田村一典