atcoder#AGC017E. [AGC017E] Jigsaw

[AGC017E] Jigsaw

配点 : 12001200

問題文

NN 個の特殊なジグソーピースがあります.それぞれのピースは,幅が 11 で高さが 11 以上の長方形のパーツを 33 つつなげた形をしています. ii 番目のピースは,次のような形をしています:

  • 高さ HH のパーツの左側に高さ AiA_i のパーツを,右側に高さ BiB_i のパーツをくっつけた形.ただし,左側のパーツの一番下の辺,右側のパーツの一番下の辺は,それぞれ中央のパーツの一番下の辺から Ci,DiC_i, D_i だけ上にある.

すぬけ君は,これらのピースを,一辺が 1010010^{100} の正方形の形をしたテーブルの上に置こうとしています.この時,次の条件を満たさなければなりません:

  • すべてのピースをテーブルの上に置く.
  • すべてのピースの中央のパーツの一番下の辺全体は,テーブルの手前の辺に接している.
  • 左右のパーツの一番下の辺全体は,テーブルの手前の辺に接しているか,他のピースを構成するあるパーツの上の辺と接している.
  • ピースを回転させたり,反転させたりして用いてはならない.

このような並べ方ができるかどうかを判定してください.

制約

  • 1N1000001 \leq N \leq 100000
  • 1H2001 \leq H \leq 200
  • 1AiH1 \leq A_i \leq H
  • 1BiH1 \leq B_i \leq H
  • 0CiHAi0 \leq C_i \leq H - A_i
  • 0DiHBi0 \leq D_i \leq H - B_i
  • 入力はすべて整数

入力

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

NN HH

A1A_1 B1B_1 C1C_1 D1D_1

A2A_2 B2B_2 C2C_2 D2D_2

:

ANA_N BNB_N CNC_N DND_N

出力

条件を満たすようにピースを並べることが可能なら YES を,不可能なら NO を出力せよ.

3 4
1 1 0 0
2 2 0 1
3 3 1 0
YES

例えば,下図のように並べればよいです.

4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
NO
10 4
1 1 0 3
2 3 2 0
1 2 3 0
2 1 0 0
3 2 0 2
1 1 3 0
3 2 0 0
1 3 2 0
1 1 1 3
2 3 0 0
YES