[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://agc017.contest.atcoder.jp/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/AT2668/085913e2ea706e9f5a234d65bf3ad02f7f07f135.png) すぬけ君は,これらのピースを,一辺が $ 10^{100} $ の正方形の形をしたテーブルの上に置こうとしています.この時,次の条件を満たさなければなりません: - すべてのピースをテーブルの上に置く. - すべてのピースの中央のパーツの一番下の辺全体は,テーブルの手前の辺に接している. - 左右のパーツの一番下の辺全体は,テーブルの手前の辺に接しているか,他のピースを構成するあるパーツの上の辺と接している. - ピースを回転させたり,反転させたりして用いてはならない. このような並べ方ができるかどうかを判定してください.

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ 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 $ ```

输出格式


If it is possible to arrange the pieces under the conditions, print `YES`; if it is impossible, print `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

输入样例 #4

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

输出样例 #4

YES

输入样例 #5

4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1

输出样例 #5

NO

输入样例 #6

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

输出样例 #6

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 $ - 入力はすべて整数 ### Problem Statement We have $ N $ irregular jigsaw pieces. Each piece is composed of three rectangular parts of width $ 1 $ and various heights joined together. More specifically: - The $ i $ -th piece is a part of height $ H $ , with another part of height $ A_i $ joined to the left, and yet another part of height $ B_i $ joined to the right, as shown below. Here, the bottom sides of the left and right parts are respectively at $ C_i $ and $ D_i $ units length above the bottom side of the center part. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2668/085913e2ea706e9f5a234d65bf3ad02f7f07f135.png) Snuke is arranging these pieces on a square table of side $ 10^{100} $ . Here, the following conditions must be held: - All pieces must be put on the table. - The entire bottom side of the center part of each piece must touch the front side of the table. - The entire bottom side of the non-center parts of each piece must either touch the front side of the table, or touch the top side of a part of some other piece. - The pieces must not be rotated or flipped. Determine whether such an arrangement is possible. ### Constraints - $ 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 $ - All input values are integers. ### Sample Explanation 1 例えば,下図のように並べればよいです. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2668/b3899e3299d8ae1d741863e0fc40f3289a6943ad.png) ### Sample Explanation 4 The figure below shows a possible arrangement. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT2668/b3899e3299d8ae1d741863e0fc40f3289a6943ad.png)