← 返回题目列表

AtCoder · kupc2012_6

F. 网络加速

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

互联网这片浩瀚的海洋正在逐渐被涂黑。
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。


作者:森悟
测试员:田村一典