레이팅 미적용JOI 街道は東西に伸びる長さL メートルの道路であり,道路の西端からl メートル(0 ≦l ≦L) 進んだ場
所は地点l と呼ばれている.
さて,今年はJOI 街道で初めてマラソン大会が開催されることとなった.このマラソン大会は通常のルー
ルとは異なり,次のようなルールに基づいて行われる.
• 道路上にN 個のボールが置かれており,i 番目(1 ≦i ≦N) のボールは地点Xi に置かれている.複数
のボールが同じ地点に置かれていることもある.
• 参加者は定められたスタート地点から出発する.
• N 個のボールをすべて持った状態で,定められたゴール地点に制限時間内にたどり着くと完走とな
る.ただし,一度持ったボールを地面に置くと失格となる.
この大会のスタート地点,ゴール地点および制限時間はまだ公開されていないが,Q 個のシナリオのいず
れかになることは既に公開されている.j 番目(1 ≦j ≦Q) のシナリオでは,スタート地点が地点S j,ゴー
ル地点が地点G j,制限時間がT j 秒である.
マラソン大会の参加者である理恵さんは,ボールを1 個拾うのに1 秒かかり,x 個のボールを持った状態
で道路上を1 メートル走るのにx + 1 秒かかる.
JOI 街道,ボール,シナリオに関する情報が与えられたとき,それぞれのシナリオについて,理恵さんが
完走する方法が存在するかを判定するプログラムを作成せよ.
• 1 ≦N ≦500 000.
• 1 ≦L ≦500 000.
• 0 ≦Xi ≦L (1 ≦i ≦N).
• 1 ≦Q ≦500 000.
• 0 ≦S j ≦L (1 ≦j ≦Q).
• 0 ≦G j ≦L (1 ≦j ≦Q).
• 1 ≦T j ≦500 000 (1 ≦j ≦Q).
• 入力される値はすべて整数である.
- (7 点) N ≦7,Q ≦10,S j = 0,G j = 0 (1 ≦j ≦Q).
- (7 点) N ≦7,Q ≦10.
- (10 点) N ≦14,Q ≦10.
- (28 点) N ≦100,Q ≦10.
- (10 点) N ≦2 000,Q ≦10.
- (19 点) N ≦2 000.
- (19 点) 追加の制約はない.
第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)
入力は以下の形式で標準入力から与えられる.
N L
X1 X2 · · · XN
Q
S 1 G1 T1
S 2 G2 T2
...
S Q GQ TQ
第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)
標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には,j 番目のシナリオにおいて理恵さんが完走する方
法が存在する場合Yes,そうでない場合No を出力せよ.
3 100
30 80 30
3
0 100 403
0 100 300
0 100 262
Yes
Yes
No
3 100
30 80 30
3
0 0 403
0 0 300
0 0 262
Yes
No
No
6 100
0 50 100 0 50 100
4
20 70 600
70 20 600
10 40 600
40 10 600
No
Yes
No
Yes