레이팅 미적용ボリビアの首都であるラパスは観光地であるとともに,ミ・テレフェリコ(Mi Telef ́erico) というロープ
ウェイ路線網でも有名である.あなたはラパスに観光に来ており,できるだけ多くの場所を観光したいと
思っている.ここで,現実を単純化した次のような状況設定を考えたい.
ラパスにはN 個のロープウェイ駅があり,標高が低い順に1 からN までの番号が付けられている.ま
た,M 個の一方通行の路線があり,1 からM までの番号が付けられている.さらに,P 個のロープウェイ
会社があり,1 からP までの番号が付けられている.各路線は1 つの会社によって管理されている.路線i
(1 ≦i ≦M) は駅Ai から駅Bi に向かって運行しており,会社Ci によって管理されている.ここで,路線は
必ず標高の低い駅から標高の高い駅に向かって運行している.すなわち,Ai < Bi が成立している.
利便性のために,ラパスの交通局はフリーパスを発行した.それぞれのフリーパスには1 ≦l ≦r ≦P を
満たす2 つの整数l, r が書かれており,会社l, l + 1, . . . , r によって管理されている路線に乗ることができる.
すなわち,1 ≦i ≦M を満たす整数i についてl ≦Ci ≦r を満たすならば路線i に乗ることができる.ここ
で,1 つのフリーパスを複数の路線で使うことも可能である.このフリーパスをフリーパス(l, r) とする.
さて,ラパスに1 からQ までの番号が付けられたQ 人の観光客が訪れた.観光客j (1 ≦j ≦Q) はフリー
パス(Lj, Rj) と,現金X j ボリビアーノを持っている.
観光客の目標は,持っているフリーパスを使って乗ることができる路線のみを用いて,駅1 から移動でき
ない駅がないようにすることである.そのために,観光客j (1 ≦j ≦Q) は以下の手順で表される交換を行
うことができる.ただし,各観光客について,交換は高々1 回しか行うことができない.
1. 1 ≦l′ ≦r′ ≦P を満たす2 つの整数l′, r′ を決める.
2. フリーパス(Lj, Rj) とフリーパス(l′, r′) を交換する.手数料として|Lj −l′| + |Rj −r′| ボリビアーノを
要する.
あなたの目的は,それぞれの観光客について,持っている現金の範囲内で目標を達成することができるか
を判定することである.
路線と観光客の情報が与えられたとき,それぞれの観光客について,持っている現金の範囲内で目標を達
成することができるかを判定するプログラムを作成せよ.
第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)
• 2 ≦N ≦300 000.
• 1 ≦M ≦300 000.
• 1 ≦P ≦109.
• 1 ≦Ai < Bi ≦N (1 ≦i ≦M).
• 1 ≦Ci ≦P (1 ≦i ≦M).
• 1 ≦Q ≦400 000.
• 1 ≦Lj ≦Rj ≦P (1 ≦j ≦Q).
• 0 ≦Xj ≦109 (1 ≦j ≦Q).
• 入力される値はすべて整数である.
- (7 点) N ≦50,M ≦50,Q ≦50,Xj = 0 (1 ≦j ≦Q).
- (8 点) P ≦10.
- (11 点) P ≦100.
- (23 点) P ≦300 000,Xj = 0 (1 ≦j ≦Q).
- (9 点) P ≦300 000.
- (22 点) N ≦8 000,M ≦8 000.
- (20 点) 追加の制約はない.
第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)
入力は以下の形式で標準入力から与えられる.
N M P
A1 B1 C1
A2 B2 C2
...
AM BM CM
Q
L1 R1 X1
L2 R2 X2
...
LQ RQ XQ
標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には,観光客j が目標を達成することができる場合は
Yes を,そうでない場合はNo を出力せよ.
第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)
4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
4
3 7 0
5 6 0
3 4 0
1 9 0
Yes
No
No
Yes
4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
3
5 6 10
3 4 1
7 8 3
Yes
No
Yes
3 1 1000000000
1 2 6
1
1 1000000000 1000000000
No
5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25
Yes
Yes
Yes
Yes
No