分数: 550 点
问题陈述
有 N 排成一排的方块,标记为 1, 2, \ldots, N 从左到右。
你被给予 M 整数对 (L_1, R_1), \ldots, (L_M, R_M).
一个正方形 j 定义为 坏 当且仅当存在一些 i 这样 L_i \leq j \leq R_i.
确定是否可以从方块移动 1 到正方形 N 通过重复执行以下操作:
- 让你当前的方块为 x。选择一个整数 i 满足以下所有条件,并移动到方块 x + i.
- A \leq i \leq B
- x + i \leq N
- 广场 x + i 还不错。
约束
- 2 \leq N \leq 10^{12}
- 0 \leq M \leq 2 \times 10^4
- 1 \leq A \leq B \leq 20
- 1 < L_i \leq R_i < N \ (1 \leq i \leq M)
- R_i < L_{i+1} \ (1 \leq i \leq M - 1)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A B L_1 R_1 L_2 R_2 \vdots L_M R_M
输出
如果可以到达广场 N 通过重复问题陈述中描述的操作,打印 Yes。否则,打印 No.
示例输入 1
24 2 3 5 7 8 17 20
示例输出 1
Yes
你可以移动到广场 N 这样: 1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24.
示例输入 2
30 1 5 8 4 24
示例输出 2
No
示例输入 3
100 4 10 11 16 18 39 42 50 55 93 99
示例输出 3
Yes