← 返回题目列表

AtCoder · awc0023_c

C. 工厂参观

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

分数: 333 分

问题陈述

高桥担任大型工厂参观导游。

工厂有 N 制造区域,每个编号从 1 to N。参观各个区域 i 正好需要 T_i 分钟。

今天, M 旅游团将参观工厂。各组 j 到达工厂时间 S_j 分钟,到达后立即访问所有号码为 L_j to R_j。团队按照区域编号递增的顺序逐一参观,参观完一个区域后立即开始参观下一个区域(区域之间没有行进时间)。

每个区域都足够宽敞,即使多个团体同时访问同一区域,也不会互相影响。

高桥想提前计算出每个小组完成所有访问的时间,并通知各小组。

对于每个小组,确定他们完成访问所有指定区域的时间(以分钟为单位)。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 0 \leq S_j \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • 所有输入值均为整数。

输入

N M
T_1 T_2 \ldots T_N
S_1 L_1 R_1
S_2 L_2 R_2
\vdots
S_M L_M R_M
  • 第一行包含区域数 N 和组数 M,用空格分隔。
  • 第二行包含访问次数 每个区域的 T_1, T_2, \ldots, T_N ,用空格分隔。
  • 以下 M 行包含每个组的信息。
  • 的 树的 (2 + j)第行包含到达时间 S_j 的 j第组,开始 L_j 并结束 R_j 要访问的区域号码范围,以空格分隔。

输出

打印 M 行。

的 树的 j- 第行应包含时间(以分钟为单位) j第一组完成所有访问。


示例输入 1

5 3
10 20 30 40 50
0 1 3
5 2 4
100 5 5

示例输出 1

60
95
150

示例输入 2

4 5
15 25 10 30
0 1 4
10 1 1
20 2 3
0 3 4
50 1 2

示例输出 2

80
25
55
40
90

示例输入 3

10 6
100 200 300 150 250 50 400 100 350 200
0 1 10
1000 3 7
500 1 5
0 6 10
200 4 6
999999999 1 1

示例输出 3

2100
2150
1500
1100
650
1000000099