AT_arc165_d.[ARC165D] Substring Comparison

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于整数列 $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)$ 。

请判断是否存在一个长度为 $N$ 的整数列 $X$ ，使得对于所有 $i=1,2,\dots,M$ ，都满足以下条件：

$X[A_i,B_i]$ 在字典序上小于 $X[C_i,D_i]$ 。

数列的字典序定义如下：设数列 $S=(S_1,S_2,\ldots,S_{|S|})$ ， $T=(T_1,T_2,\ldots,T_{|T|})$ ，若满足以下 1. 或 2. 中的任意一个，则称 $S$ 在字典序上小于 $T$ 。其中 $|S|,|T|$ 分别表示 $S,T$ 的长度。

$|S|<|T|$ 且 $(S_1,S_2,\ldots,S_{|S|})=(T_1,T_2,\ldots,T_{|S|})$ 。
存在整数 $1\leq i\leq \min\lbrace |S|,|T| \rbrace$ $1 \leq i \leq min {∣ S ∣, ∣ T ∣}$ ，使得以下两点都成立：
- $(S_1,S_2,\ldots,S_{i-1})=(T_1,T_2,\ldots,T_{i-1})$
- $S_i$ 小于 $T_i$ （作为数值比较）。

输入格式

输入按以下格式从标准输入读入。

$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
```
输入#2
```
3 2
1 2 2 3
2 2 1 1
```
输出#2
```
No
```

输入#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

说明/提示

数据范围

$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$
输入的所有值均为整数

样例解释 1

例如 $X=(1,1,2,1)$ 就满足所有条件。

样例解释 2

不存在满足条件的整数列 $X$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页