マラソン大会 2 (Marathon Race 2)

JOI 街道は東西に伸びる長さ \(L\) メートルの道路であり，道路の西端から \(l\) メートル (\(0 \leqq l \leqq L\)) 進んだ場所は地点 \(l\) と呼ばれている．

さて，今年は JOI 街道で初めてマラソン大会が開催されることとなった．このマラソン大会は通常のルールとは異なり，次のようなルールに基づいて行われる．

• 道路上に \(N\) 個のボールが置かれており，\(i\) 番目 (\(1 \leqq i \leqq N\)) のボールは地点 \(X_i\) に置かれている．複数のボールが同じ地点に置かれていることもある．
• 参加者は定められたスタート地点から出発する．
• \(N\) 個のボールをすべて持った状態で，定められたゴール地点に制限時間内にたどり着くと完走となる．ただし，一度持ったボールを地面に置くと失格となる．

この大会のスタート地点，ゴール地点および制限時間はまだ公開されていないが，\(Q\) 個のシナリオのいずれかになることは既に公開されている． \(j\) 番目 (\(1 \leqq j \leqq Q\)) のシナリオでは，スタート地点が地点 \(S_j\)，ゴール地点が地点 \(G_j\)，制限時間が \(T_j\) 秒である．

マラソン大会の参加者である理恵さんは，ボールを \(1\) 個拾うのに \(1\) 秒かかり，\(x\) 個のボールを持った状態で道路上を \(1\) メートル走るのに \(x+1\) 秒かかる．

JOI 街道，ボール，シナリオに関する情報が与えられたとき，それぞれのシナリオについて，理恵さんが完走する方法が存在するかを判定するプログラムを作成せよ．

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

\(N\) \(L\)
\(X_1\) \(X_2\) \(\cdots\) \(X_N\)
\(Q\)
\(S_1\) \(G_1\) \(T_1\)
\(S_2\) \(G_2\) \(T_2\)
\(\vdots\)
\(S_Q\) \(G_Q\) \(T_Q\)

標準出力に \(Q\) 行で出力せよ． \(j\) 行目 (\(1 \leqq j \leqq Q\)) には，\(j\) 番目のシナリオにおいて理恵さんが完走する方法が存在する場合 Yes，そうでない場合 No を出力せよ．

• \(1 \leqq N \leqq 500\,000\)．
• \(1 \leqq L \leqq 500\,000\)．
• \(0 \leqq X_i \leqq L\) (\(1 \leqq i \leqq N\))．
• \(1 \leqq Q \leqq 500\,000\)．
• \(0 \leqq S_j \leqq L\) (\(1 \leqq j \leqq Q\))．
• \(0 \leqq G_j \leqq L\) (\(1 \leqq j \leqq Q\))．
• \(1 \leqq T_j \leqq 500\,000\) (\(1 \leqq j \leqq Q\))．
• 入力される値はすべて整数である．

1. (\(7\) 点) \(N \leqq 7\)，\(Q \leqq 10\)，\(S_j = 0\)，\(G_j = 0\) (\(1 \leqq j \leqq Q\))．
2. (\(7\) 点) \(N \leqq 7\)，\(Q \leqq 10\)．
3. (\(10\) 点) \(N \leqq 14\)，\(Q \leqq 10\)．
4. (\(28\) 点) \(N \leqq 100\)，\(Q \leqq 10\)．
5. (\(10\) 点) \(N \leqq 2\,000\)，\(Q \leqq 10\)．
6. (\(19\) 点) \(N \leqq 2\,000\)．
7. (\(19\) 点) 追加の制約はない．

JOI 2024 · JCIOI · CC BY-SA 4.0