[AGC017E] Jigsaw
题意翻译
- 你有$N$块拼图,每块拼图分为左 中 右三个部分,其中中间部分高度恒为$H$,左右部分的形状将由$A_i,B_i,C_i,D_i$指定,$A_i,B_i$指定左右部分长度,$C_i,D_i$指定左右部分离地高度.
- 现在,你需要将这$N$块拼图拼成一条直线,使得每块拼图中间部分接地,左右部分不悬空。
- 一个不合法方案
| | a | |
| :----------: | :----------: | :----------: |
| a | a | a |
| | a | |
- 一个合法方案(a,b为两块拼图)
| | a | | b | |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| | a | b | b | b |
| a | a | a | b | b |
题目描述
[problemUrl]: https://atcoder.jp/contests/agc017/tasks/agc017_e
$ N $ 個の特殊なジグソーピースがあります.それぞれのピースは,幅が $ 1 $ で高さが $ 1 $ 以上の長方形のパーツを $ 3 $ つつなげた形をしています. $ i $ 番目のピースは,次のような形をしています:
- 高さ $ H $ のパーツの左側に高さ $ A_i $ のパーツを,右側に高さ $ B_i $ のパーツをくっつけた形.ただし,左側のパーツの一番下の辺,右側のパーツの一番下の辺は,それぞれ中央のパーツの一番下の辺から $ C_i,\ D_i $ だけ上にある.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_agc017_e/085913e2ea706e9f5a234d65bf3ad02f7f07f135.png)
すぬけ君は,これらのピースを,一辺が $ 10^{100} $ の正方形の形をしたテーブルの上に置こうとしています.この時,次の条件を満たさなければなりません:
- すべてのピースをテーブルの上に置く.
- すべてのピースの中央のパーツの一番下の辺全体は,テーブルの手前の辺に接している.
- 左右のパーツの一番下の辺全体は,テーブルの手前の辺に接しているか,他のピースを構成するあるパーツの上の辺と接している.
- ピースを回転させたり,反転させたりして用いてはならない.
このような並べ方ができるかどうかを判定してください.
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ H $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ : $ A_N $ $ B_N $ $ C_N $ $ D_N $
输出格式
条件を満たすようにピースを並べることが可能なら `YES` を,不可能なら `NO` を出力せよ.
输入输出样例
输入样例 #1
3 4
1 1 0 0
2 2 0 1
3 3 1 0
输出样例 #1
YES
输入样例 #2
4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
输出样例 #2
NO
输入样例 #3
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
输出样例 #3
YES
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 100000 $
- $ 1\ \leq\ H\ \leq\ 200 $
- $ 1\ \leq\ A_i\ \leq\ H $
- $ 1\ \leq\ B_i\ \leq\ H $
- $ 0\ \leq\ C_i\ \leq\ H\ -\ A_i $
- $ 0\ \leq\ D_i\ \leq\ H\ -\ B_i $
- 入力はすべて整数
### Sample Explanation 1
例えば,下図のように並べればよいです. !\[\](https://atcoder.jp/img/agc017/27db184b6924d4cec5077a54b505706a.png)