問題一覧 > 通常問題

No.274 The Wall

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 221
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
10 ProblemId : 658 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:37

問題文

$1 \times 1$のブロックが横に$M個$連なった$1 \times M$のブロックがある。
ブロックは基本白色であるが左からL番目から左からR番目(0-index)までの連続したブロックはピンク色である。
ブロックは180度回転することもできる(90度回転はできません)。
すなわち、以下の図のようなものである。



横の長さが同じ$1 \times M$のN本のブロックが与えられる。
それぞれのブロックはそれぞれピンク色の連続した領域を1つ持つ。
N本のブロックを上に積んでいき良い壁を作りたい。
良い壁とは縦の列でブロックを見たときピンク色のブロックが1つ以下のものをいう。

例えば、$1 \times 6$のブロックを4つ積んだときの良い壁と悪い壁の例。


左の壁は縦にブロックを見たときにピンク色のブロックが無いか1つのピンク色のブロックがある良い壁である。
一方、右の壁は縦で見たときピンク色のブロックが2つ以上ある場合があり悪い壁である。

いずれのブロックにも180度回転を好きなだけ行うことができる。
与えられるN本のブロックをすべて積んで良い壁を作れるか判定せよ。

入力

$N$ $M$
$L_0$ $R_0$
$L_1$ $R_1$
$ \vdots\ $
$L_{N-1}$ $R_{N-1}$

$N$は$1 \times M$のブロックの本数。$2\le N \le 2000$。
$M$は1本のブロックの横のブロック数。$2\le M \le 4000$。
$L_i$は$i$番目のブロックのピンク領域の最左のブロック位置。
$R_i$は$i$番目のブロックのピンク領域の最右のブロック位置。
$0\le L_i \le R_i \le {M-1}$。

出力

良い壁ができる時には"YES" 、できないときには"NO"を1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 6
5 5
2 3
4 4
1 1
出力
YES

問題文中の良い壁の例と同じ。
どのブロックも180度回転させずに積めば良い壁になる。
0番目のブロックを180度回転させても良い壁には変わりない。

サンプル2
入力
4 6
3 5
3 4
4 4
1 2
出力
NO

問題文中の悪い壁の例と同じ。
180度回転をどのように使っても良い壁はできない。

サンプル3
入力
2 4
0 1
0 1
出力
YES

どちらかのブロックを180度回転させて積めば良い壁になる。

サンプル4
入力
5 10
8 8
0 0
2 4
2 3
8 8
出力
YES

良い壁にできます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。