← 返回题目列表

AtCoder · abc388_f

I. 危险的双六

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

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