레이팅 미적용N + 1 層からなるダンジョンがあり,ダンジョン内にはM 人のプレイヤーがいる.ダンジョンの階層に
は入口から近い順に第1 層から第N + 1 層までの番号が付いている.また,プレイヤーには1 からM まで
の番号が付いている.
ダンジョンのある階層から次の階層へ進むには体力を要する.プレイヤーは,第i 層(1 ≦i ≦N) から第
i + 1 層に進む際に体力をAi 消費する.また,このダンジョンは一方通行であり,可能な階層間の移動は第
i 層(1 ≦i ≦N) から第i + 1 層への移動のみである.
第1 層から第N 層までの各階層には1 つの回復の泉がある.第i 層(1 ≦i ≦N) にある回復の泉では,プ
レイヤーはBi 枚のコインを消費することで体力を1 回復させることができる.回復の泉は,コインがある
限り何回でも使用することができる.ただし,プレイヤーの体力には上限があり,回復の泉を使っても,体
力がその上限を超えることはない.
プレイヤーj (1 ≦j ≦M) は現在第S j 層にいる.現在の体力は0 であり,体力の上限はU j である.プレ
イヤーj は,体力を0 未満にすることなく第T j 層まで進もうとしている.そのためには何枚のコインが必
要であろうか.
ダンジョンの情報と各プレイヤーの情報が与えられたとき,各プレイヤーが体力を0 未満にせずに目標の
階層まで進むことが可能かを判定し,可能な場合には必要なコインの枚数の最小値を求めるプログラムを作
成せよ.
• 1 ≦N ≦200 000.
• 1 ≦M ≦200 000.
• 1 ≦Ai ≦200 000 (1 ≦i ≦N).
• 1 ≦Bi ≦200 000 (1 ≦i ≦N).
• 1 ≦S j < T j ≦N + 1 (1 ≦j ≦M).
• 1 ≦U j ≦100 000 000 (1 ≦j ≦M).
- (11 点) N ≦3 000,M ≦3 000.
- (14 点) U1 = U2 = · · · = UM.
- (31 点) T j = N + 1 (1 ≦j ≦M).
- (44 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M
A1 · · · AN
B1 · · · BN
S 1 T1 U1
...
S M TM UM
第20 回日本情報オリンピック(JOI 2020/2021) 本選
2021 年2 月14 日(オンライン開催)
標準出力にM 行で出力せよ.第j 行目(1 ≦j ≦M) にはプレイヤーj が第T j 層まで進むために必要なコ
インの枚数の最小値を出力せよ. ただし, プレイヤーj が第T j 層まで進むことができない場合は−1 を出力
せよ.
5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9
-1
29
3
22
10 10
1 8 9 8 1 5 7 10 6 6
10 10 2 8 10 3 9 8 3 7
2 11 28
5 11 28
7 11 28
1 11 18
3 11 18
8 11 18
4 11 11
6 11 11
10 11 11
9 11 5
208
112
179
248
158
116
234
162
42
-1
20 20
2 3 2 11 4 6 9 15 17 14 8 17 3 12 20 4 19 8 4 5
19 3 18 2 13 7 5 19 10 1 12 8 1 15 20 1 13 2 18 6
12 15 67
7 15 18
16 17 14
9 21 97
1 19 43
3 18 31
16 20 70
7 20 28
1 16 61
3 5 69
9 10 15
2 13 134
11 19 23
16 20 14
5 21 16
15 20 11
7 11 54
7 16 16
13 17 10
3 15 135
151
591
4
284
339
517
35
581
254
58
-1
178
519
-1
-1
-1
219
-1
-1
214