레이팅 미적용JOI 村にはN 個の区画があり,1 からN までの番号が付いている.これらの区画は番号順に一列に並ん
でいる.今,各区画では火事が発生しており,時刻0 における区画i (1 ≦i ≦N) の火の強さはS i (S i > 0)
である.
時刻0 に,区画1 から区画N の方向に風が吹き始めた.隣り合う2 つの区画について,時刻t (0 ≦t) に
おいて風上の区画の火が風下の区画の火より強いとき,時刻t + 1 における風下の区画の火の強さは,時刻
t における風上の区画の火の強さと同じになってしまう.そうでないときは,時刻t + 1 における風下の区
画の火の強さは,時刻t と同じである.すなわち,時刻t (0 ≦t) における区画i (1 ≦i ≦N) の火の強さを
S i(t) と書くとすると,1 ≦t ならば,S i(t) = max{S i−1(t −1), S i(t −1)} となる.ただし,任意のt (0 ≦t) に
対して,S 0(t) = 0 とし,任意のi (1 ≦i ≦N) に対しS i(0) = S i とする.
消防士であるあなたはQ 個の消火活動を計画した.Q 個の計画のうちどれか1 つだけを実施する予定で
ある.j 番目の計画(1 ≦j ≦Q) は,時刻T j に,L j ≦k ≦R j となるすべての区画k に消火剤を撒き,それ
らの区画を消火するというものである.火の強さがs である区画を消火するためにはs リットルの消火剤
が必要である.つまり,j 番目の計画の消火活動にはS Lj(T j) + S L j+1(T j) + · · · + S Rj(T j) リットルの消火剤
が必要である.
どの計画を実行するか吟味するためにも,各計画に必要な消火剤の量が知りたい.
時刻0 における火の強さの情報と消火活動の計画の情報が与えられたとき,各計画に必要な消火剤の量
を求めるプログラムを作成せよ.
• 1 ≦N ≦200 000.
• 1 ≦Q ≦200 000.
• 1 ≦S i ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦T j ≦N (1 ≦j ≦Q).
• 1 ≦L j ≦R j ≦N (1 ≦j ≦Q).
- (1 点) N ≦200,Q ≦200.
- (6 点) T1 = T2 = · · · = TQ.
- (7 点) L j = R j (1 ≦j ≦Q).
- (6 点) S i ≦2 (1 ≦i ≦N).
- (80 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N Q
S 1 . . . S N
T1 L1 R1
...
TQ LQ RQ
標準出力にQ 行で出力せよ.第j 行目(1 ≦j ≦Q) にはj 番目の計画に必要な消火剤の量を出力せよ.
第19 回日本情報オリンピック(JOI 2019/2020) 本選
2020 年2 月9 日(茨城県つくば市)
5 5
9 3 2 6 5
1 1 3
2 1 5
3 2 5
4 3 3
5 3 5
21
39
33
9
27
10 10
3 1 4 1 5 9 2 6 5 3
1 1 6
2 8 10
4 2 7
8 3 3
6 1 10
3 2 8
5 1 9
7 4 5
9 7 9
10 10 10
28
21
34
4
64
43
55
9
27
9
10 10
3 1 4 1 5 9 2 6 5 3
1 6 6
2 8 8
4 2 2
8 3 3
6 1 1
3 4 4
5 5 5
7 10 10
9 8 8
10 7 7
9
9
3
4
3
4
5
9
9
9
10 10
3 1 4 1 5 9 2 6 5 3
7 1 6
7 8 10
7 2 7
7 3 3
7 1 10
7 2 8
7 1 9
7 4 5
7 7 9
7 10 10
28
27
34
4
64
43
55
9
27
9
20 20
2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1
1 1 14
2 3 18
4 10 15
8 2 17
9 20 20
4 8 19
7 2 20
11 1 5
13 2 8
20 1 20
2 12 15
7 1 14
12 7 18
14 2 17
9 19 20
12 12 12
6 2 15
11 2 15
19 12 17
4 1 20
25
30
12
32
2
24
38
10
14
40
8
28
24
32
4
2
28
28
12
40