← 返回题目列表

Codeforces · 1284/D

D. 新年和会议

中文机器翻译题面 查看原题

充满乐观的Hyunuk将主持一场会议,讲述新的一年将会多么美好!

会议将有 $$$n$$$ 讲座。 Hyunuk 有两个候选场地 $$$a$$$ 和 $$$b$$$。对于 $$$n$$$ 讲座中的每一堂课,演讲者指定了两个时间间隔 $$$[sa_i, ea_i]$$$ ($$$sa_i \le ea_i$$$) 和 $$$[sb_i, eb_i]$$$ ($$$sb_i \le eb_i$$$)。如果会议在会场$$$a$$$举行,讲座将从$$$sa_i$$$到$$$ea_i$$$举行,如果会议在会场$$$b$$$举行,讲座将从$$$sb_i$$$到$$$eb_i$$$举行。 Hyunuk 将选择其中一个场地,所有讲座都将在该场地举行。

如果两个讲座在时间上有任何共同点,则称它们重叠。形式上,当且仅当 $$$\max(x, u) \le \min(y, v)$$$ 时,间隔 $$$[x, y]$$$ 举行的讲座与间隔 $$$[u, v]$$$ 举行的讲座重叠。

如果 $$$s$$$ 中的讲座不成对重叠(即没有两个讲座重叠),则我们说参与者可以参加讲座的子集 $$$s$$$。请注意,出席的可能性可能取决于 Hyunuk 是否选择地点 $$$a$$$ 或地点 $$$b$$$ 举行会议。

如果对于其中一个场地,参与者可以参加 $$$s$$$,但对于另一个场地,参与者不能参加 $$$s$$$,则称讲座 $$$s$$$ 的子集是场地敏感的。

场地敏感集对于有兴趣参加 $$$s$$$ 讲座的参与者来说是有问题的,因为参与者无法确定讲座时间是否会重叠。当且仅当没有场地敏感的场景时,Hyunuk 才会感到高兴。确定Hyunuk是否会幸福。

输入

第一行包含一个整数$$$n$$$ ($$$1 \le n \le 100\,000$$$),会议举办的讲座数量。

接下来的 $$$n$$$ 行包含四个整数 $$$sa_i$$$, $$$ea_i$$$, $$$sb_i$$$, $$$eb_i$$$ ($$$1 \le sa_i, ea_i, sb_i, eb_i \le 10^9$$$, $$$sa_i \le ea_i, sb_i \le eb_i$$$)。

输出

如果 Hyunuk 高兴,请打印“是”。否则打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

2
1 2 3 6
3 4 7 8

输出 #1

YES

输入 #2

3
1 3 2 4
4 5 6 7
3 4 5 5

输出 #2

NO

输入 #3

6
1 5 2 9
2 4 5 8
3 6 7 11
7 10 12 16
8 11 13 17
9 12 14 18

输出 #3

YES

注意

在第二个示例中,讲座集 $$$\{1, 3\}$$$ 是场地敏感的。因为参加者不能在会场$$$a$$$参加本次讲座,但可以在会场$$$b$$$参加。

在第一和第三示例中,场地敏感集不存在。