分数: 700 点
问题陈述
对于整数序列 X=(X_1,X_2,\dots,X_n),让 X[L,R] 表示整数序列 (X_L,X_{L+1},\dots,X_{R}).
给你整数 N 和 M,和 M 整数的四元组 (A_i,B_i,C_i,D_i).
判断是否存在整数序列 X 长度 N 满足以下每个条件 i=1,2,\dots,M:
- X[A_i,B_i] 按字典顺序小于 X[C_i,D_i].
序列的字典顺序是什么?
一个序列 非负整数的 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比 T = (T_1,T_2,\ldots,T_{|T|}) 当下面的 1. 或 2. 成立时。 在这里, |S| 和 |T| 表示的长度 S 和 T。
- |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 满足以下两个条件:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i 小于 T_i (作为数字)。
约束
- 2 \leq N \leq 2000
- 1 \leq M \leq 2000
- 1 \leq A_i \leq B_i \leq N
- 1 \leq C_i \leq D_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_M B_M C_M D_M
输出
如果某个整数序列满足条件,则打印 Yes;否则,打印 No.
示例输入 1
4 2 1 3 3 4 4 4 1 2
示例输出 1
Yes
例如, X=(1,1,2,1) 满足条件。
示例输入 2
3 2 1 2 2 3 2 2 1 1
示例输出 2
No
无整数序列 X 满足条件。
示例输入 3
15 20 2 5 6 14 11 14 10 10 13 15 6 10 8 10 3 8 7 8 1 9 2 8 14 15 14 14 5 12 6 10 9 9 1 4 10 14 5 14 6 7 8 10 5 8 8 10 11 15 4 8 4 11 7 9 1 4 8 10 3 3 11 13 8 14 6 13 4 15 4 7 6 11 2 5 1 2 8 14 6 8
示例输出 3
No