ミ・テレフェリコ (Mi Teleférico)

Unrated

日本語

Language

Time limit: 2000 ms
Memory limit: 1024 MB
Submissions: 0
Correct: 0
Solved by: 0
AC rate: —

Statement

ボリビアの首都であるラパスは観光地であるとともに，ミ・テレフェリコ(Mi Teleférico)というロープウェイ路線網でも有名である．あなたはラパスに観光に来ており，できるだけ多くの場所を観光したいと思っている．ここで，現実を単純化した次のような状況設定を考えたい．

ラパスには \(N\) 個のロープウェイ駅があり，標高が低い順に \(1\) から \(N\) までの番号が付けられている．また，\(M\) 個の一方通行の路線があり，\(1\) から \(M\) までの番号が付けられている．さらに，\(P\) 個のロープウェイ会社があり，\(1\) から \(P\) までの番号が付けられている．各路線は \(1\) つの会社によって管理されている．路線 \(i\) (\(1 \leqq i \leqq M\)) は駅 \(A_i\) から駅 \(B_i\) に向かって運行しており，会社 \(C_i\) によって管理されている．ここで，路線は必ず標高の低い駅から標高の高い駅に向かって運行している．すなわち，\(A_i < B_i\) が成立している．

利便性のために，ラパスの交通局はフリーパスを発行した．それぞれのフリーパスには \(1 \leqq l \leqq r \leqq P\) を満たす \(2\) つの整数 \(l, r\) が書かれており，会社 \(l, l + 1, \dots, r\) によって管理されている路線に乗ることができる．すなわち，\(1 \leqq i \leqq M\) を満たす整数 \(i\) について \(l \leqq C_i \leqq r\) を満たすならば路線 \(i\) に乗ることができる．ここで，\(1\) つのフリーパスを複数の路線で使うことも可能である．このフリーパスをフリーパス \((l, r)\) とする．

さて，ラパスに \(1\) から \(Q\) までの番号が付けられた \(Q\) 人の観光客が訪れた．観光客 \(j\) (\(1 \leqq j \leqq Q\)) はフリーパス \((L_j, R_j)\) と，現金 \(X_j\) ボリビアーノを持っている．

観光客の目標は，持っているフリーパスを使って乗ることができる路線のみを用いて，駅 \(1\) から移動できない駅がないようにすることである．そのために，観光客 \(j\) (\(1 \leqq j \leqq Q\)) は以下の手順で表される交換を行うことができる．ただし，各観光客について，交換は高々 \(1\) 回しか行うことができない．

\(1 \leqq l' \leqq r' \leqq P\) を満たす \(2\) つの整数 \(l', r'\) を決める．
フリーパス \((L_j, R_j)\) とフリーパス \((l', r')\) を交換する．手数料として \(|L_j - l'| + |R_j - r'|\) ボリビアーノを要する．

あなたの目的は，それぞれの観光客について，持っている現金の範囲内で目標を達成することができるかを判定することである．

路線と観光客の情報が与えられたとき，それぞれの観光客について，持っている現金の範囲内で目標を達成することができるかを判定するプログラムを作成せよ．

Input

入力は以下の形式で標準入力から与えられる．

\(N\) \(M\) \(P\)
\(A_1\) \(B_1\) \(C_1\)
\(A_2\) \(B_2\) \(C_2\)
\(\vdots\)
\(A_M\) \(B_M\) \(C_M\)
\(Q\)
\(L_1\) \(R_1\) \(X_1\)
\(L_2\) \(R_2\) \(X_2\)
\(\vdots\)
\(L_Q\) \(R_Q\) \(X_Q\)

Output

標準出力に \(Q\) 行で出力せよ．\(j\) 行目 (\(1 \leqq j \leqq Q\)) には，観光客 \(j\) が目標を達成することができる場合は Yes を，そうでない場合は No を出力せよ．

Constraints

\(2 \leqq N \leqq 300\,000\)．
\(1 \leqq M \leqq 300\,000\)．
\(1 \leqq P \leqq 10^9\)．
\(1 \leqq A_i < B_i \leqq N\) (\(1 \leqq i \leqq M\))．
\(1 \leqq C_i \leqq P\) (\(1 \leqq i \leqq M\))．
\(1 \leqq Q \leqq 400\,000\)．
\(1 \leqq L_j \leqq R_j \leqq P\) (\(1 \leqq j \leqq Q\))．
\(0 \leqq X_j \leqq 10^9\) (\(1 \leqq j \leqq Q\))．
入力される値はすべて整数である．

Subtasks

(\(7\) 点) \(N \leqq 50\)，\(M \leqq 50\)，\(Q \leqq 50\)，\(X_j = 0\) (\(1 \leqq j \leqq Q\))．
(\(8\) 点) \(P \leqq 10\)．
(\(11\) 点) \(P \leqq 100\)．
(\(23\) 点) \(P \leqq 300\,000\)，\(X_j = 0\) (\(1 \leqq j \leqq Q\))．
(\(9\) 点) \(P \leqq 300\,000\)．
(\(22\) 点) \(N \leqq 8\,000\)，\(M \leqq 8\,000\)．
(\(20\) 点) 追加の制約はない．

Examples

Sample input 1

Sample output 1

Yes
No
No
Yes

まず，観光客 \(1\) については，最初フリーパス \((3, 7)\) と現金 \(0\) ボリビアーノを持っている．この観光客は，フリーパスの交換を行わないことで目標を達成できる．なぜなら，フリーパス \((3, 7)\) により乗ることができる路線は \(1, 2, 3, 4\) の \(4\) つであり，この \(4\) つの路線を用いて，以下のように駅 \(1\) から各駅に移動することができるからである．

路線 \(3\) を用いることで，駅 \(1 \to 2\) と移動することができる．
路線 \(1, 4\) をこの順に用いることで，駅 \(1 \to 2 \to 3\) と移動することができる．
路線 \(3, 2\) をこの順に用いることで，駅 \(1 \to 2 \to 4\) と移動することができる．

したがって，\(1\) 行目に Yes を出力する．

次に，観光客 \(2\) については，最初フリーパス \((5, 6)\) と現金 \(0\) ボリビアーノを持っているが，この観光客は目標を達成することができない．なぜなら，フリーパス \((5, 6)\) により乗ることができる路線は路線 \(3, 4\) の \(2\) つのみであり，この \(2\) つの路線を用いて，駅 \(1\) から駅 \(4\) へ移動することができないからである．また，現金を \(0\) ボリビアーノしか持っていないため，異なるフリーパスと交換することができないからである．

したがって，\(2\) 行目に No を出力する．

さらに，観光客 \(3\) については目標を達成することができず，観光客 \(4\) については目標を達成することができるため，\(3\) 行目に No を出力し，\(4\) 行目に Yes を出力する．

この入力例はすべての小課題の制約を満たす．

Sample input 2

Sample output 2

Yes
No
Yes

路線の情報は入力例 \(1\) と同じである．

まず，観光客 \(1\) については最初フリーパス \((5, 6)\) と現金 \(10\) ボリビアーノを持っている．この観光客は，フリーパスの交換を次のように行うことで目標を達成できる．

\(1 \leqq l' \leqq r' \leqq P\) を満たす \(2\) つの整数として \(l' = 1, r' = 5\) と決める．
フリーパス \((5, 6)\) とフリーパス \((1, 5)\) を交換する．手数料として \(|5-1|+|6-5|=5\) ボリビアーノを要する．

したがって，\(1\) 行目に Yes を出力する．

次に，観光客 \(2\) については最初フリーパス \((3, 4)\) と現金 \(1\) ボリビアーノを持っている．この観光客はどのようなフリーパスの交換を行っても，目標を達成することができない．

したがって，\(2\) 行目に No を出力する．

さらに，観光客 \(3\) については目標を達成することができるため，\(3\) 行目に Yes を出力する．

この入力例は小課題 \(2,3,5,6,7\) の制約を満たす．

Sample input 3

3 1 1000000000
1 2 6
1
1 1000000000 1000000000

Sample output 3

No

この路線において，駅 \(1\) から駅 \(3\) へ移動することができない．したがって，フリーパスによらず，観光客は目標を達成することはできない．

この入力例は小課題 \(6,7\) の制約を満たす．

Sample input 4

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

Sample output 4

Yes
Yes
Yes
Yes
No

この入力例は小課題 \(5,6,7\) の制約を満たす．

Notes

JOI 2025 · JCIOI · CC BY-SA 4.0

Source

Olympiad › Japanese Olympiad in Informatics › JOI 2024-2025 Season › JOI 2025 Final Round3