306998: CF1284D. New Year and Conference
Memory Limit：1024 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
New Year and Conference
题意翻译
#### 题目描述 充满快乐的，Hyunuk将要举办一个关于将来的一年有多伟大的大会！ 大会有 $n$ 个讲座。Hyunuk有两个可供选择的会场$a$和$b$。对于n个讲座中的每一个，演讲者选择了两个时间区间$[sa_{i},ea_{i}]$（$sa_{i} \leq ea_{i}$）和$[sb_{i},eb_{i}]$（$sb_{i} \leq eb_{i}$）。如果大会在a会场举办，那么讲座就会在$sa_{i}$到$ea_{i}$的时间举行；如果大会在b会场举行，那么该讲座就会在$sb_{i}$到$eb_{i}$的时间举行。Hyunuk只能选定两个会场中的一个，然后所有讲座都要在那个会场举行。 两个讲座被称为冲突，当且仅当它们共用了同一个时间点。正式地，我们称一个在区间$[x,y]$中举办的讲座和一个在$[u,v]$区间举办的讲座冲突，当且仅当$\max(x,u) \leq \min(y,v)$。 我们称一个听众可以参加所有讲座的一个子集$s$，当且仅当这个子集中任何一对讲座都不冲突。注意：是否能参加这个子集$s$的可能取决于Hyunuk选择的是$a$会场或是$b$会场来举办大会 对于一个子集$s$，若在一个会场，观众可以参加，而在另一个会场，观众却不可以参加，那么它被称为“会场敏感的”。 对于观众来说，是否存在一个会场敏感的子集$s$是一个重要的问题，因为观众无法确定讲座时间是否会冲突。Hyunuk会开心当且仅当不存在任意一个会场敏感的子集。请判断Hyunuk是否会开心 #### 输入格式 第一行包含1个整数$n$，表示讲座的数目； 接下来的$n$行，每行4个整数$sa_{i}$,$ea_{i}$,$sb_{i}$,$eb_{i}$($1$$\leq $$sa_{i}$,$ea_{i}$,$sb_{i}$,$eb_{i}$$\leq$$10^9$，$sa_{i} \leq ea_{i}$，$sb_{i} \leq eb_{i}$） #### 输出格式 当Hyunuk开心时，输出"YES"，否则输出"NO"。注：答案是大小写不敏感的。题目描述
Filled with optimism, Hyunuk will host a conference about how great this new year will be! The conference will have $ n $ lectures. Hyunuk has two candidate venues $ a $ and $ b $ . For each of the $ n $ lectures, the speaker specified two time intervals $ [sa_i, ea_i] $ ( $ sa_i \le ea_i $ ) and $ [sb_i, eb_i] $ ( $ sb_i \le eb_i $ ). If the conference is situated in venue $ a $ , the lecture will be held from $ sa_i $ to $ ea_i $ , and if the conference is situated in venue $ b $ , the lecture will be held from $ sb_i $ to $ eb_i $ . Hyunuk will choose one of these venues and all lectures will be held at that venue. Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval $ [x, y] $ overlaps with a lecture held in interval $ [u, v] $ if and only if $ \max(x, u) \le \min(y, v) $ . We say that a participant can attend a subset $ s $ of the lectures if the lectures in $ s $ do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue $ a $ or venue $ b $ to hold the conference. A subset of lectures $ s $ is said to be venue-sensitive if, for one of the venues, the participant can attend $ s $ , but for the other venue, the participant cannot attend $ s $ . A venue-sensitive set is problematic for a participant who is interested in attending the lectures in $ s $ because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy.输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1 \le n \le 100\,000 $ ), the number of lectures held in the conference. Each of the next $ n $ lines contains four integers $ 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 $ ).
输出格式
Print "YES" if Hyunuk will be happy. Print "NO" otherwise. You can print each letter in any case (upper or lower).
输入输出样例
输入样例 #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