実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 500 点
問題文
N 個のハードルが数直線上に置かれている。i 番目のハードルの位置は x_i で、 x_i は正の整数かつ x_1 < x_2 < … < x_N を満たす。
あなたはハードル走の走者である。あなたは数直線上の原点から正の方向に一定の速度で走って進む。途中で走る向きを変えることはできない。あなたは任意の位置(整数座標でなくともよい)でジャンプすることができる。ジャンプすると、そこから L メートルの間空中を移動したのち着地する。しかしジャンプは体力を使うので、着地してから L メートルの間はジャンプできず、地上を走らなければならない。最初、あなたは地上にいる。
あなたはハードルに当たることなくすべてのハードルを飛び越えることができるか?
ただし、位置 x にあるハードルを飛び越えるとは、位置 x で空中にいることである。また、ジャンプする位置、着地する位置ではあなたは地上にいるものとする。つまり、ハードルのある位置でジャンプしたり、ハードルのある位置に着地することはできない。原点でジャンプすることはできる。
制約
- 入力は全て整数である。
- 1 ≦ N ≦ 10^5
- 1 ≦ L ≦ 10^9
- 1 ≦ x_1 < x_2 < … < x_N ≦ 10^9
部分点
400 点分のテストケースでは、以下のすべてが満たされる。
- 1 ≦ N ≦ 2000
- 1 ≦ L ≦ 2000
- 1 ≦ x_1 < x_2 < … < x_N ≦ 2000
入力
入力は以下の形式で標準入力から与えられる。
N L x_1 x_2 : x_N
出力
ハードルに当たることなくすべてのハードルを飛び越えることができる場合は”YES”(ダブルクオーテーションは不要), そうでない場合は”NO”を出力せよ。
入力例 1
3 4 3 5 13
出力例 1
YES
図1: 入力例1での飛び方の例
図1の赤い線はハードルを、青い線はすべてのハードルを飛び越えるための進み方の一例を示している。 この進み方では、まず 0 ≦ x ≦ 1.2 では地上を走る。 次に、x = 1.2 でジャンプする。すると 1.2 < x < 5.2 では空中を進む。ジャンプの影響により、 5.2 ≦ x ≦ 9.2 では地上を走らなければならない。 その後 x = 11 でジャンプすると、すべてのハードルを飛び越えることができる。
このケースは部分点の制約を満たす。
入力例 2
5 3 1 2 5 7 9
出力例 2
NO
どのようにジャンプしても位置 x = 5 のハードルを飛び越えることはできない。
このケースは部分点の制約を満たす。
入力例 3
5 6 1 2 3 4 5
出力例 3
YES
たとえば原点でジャンプするとすべてのハードルを飛び越えることができる。
このケースは部分点の制約を満たす。
入力例 4
3 5 1 3 10
出力例 4
NO
原点から負の方向に移動することはできない。
このケースは部分点の制約を満たす。
入力例 5
4 4 2 3 9 15
出力例 5
NO
このケースは部分点の制約を満たす。
入力例 6
4 1 1 3 5 7
出力例 6
YES
このケースは部分点の制約を満たす。
入力例 7
4 6100991 199010 199110 6300101 9231211
出力例 7
NO