← 返回题目列表

AtCoder · arc165_d

D. 子串比较

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

分数: 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。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 有一个整数 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