F - Dangerous Sugoroku Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

N 個のマスが 1 列に並んでおり、順に 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

マス 1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24 のように移動することでマス N に移動することができます。

入力例 2

30 1 5 8
4 24

出力例 2

No

入力例 3

100 4 10 11
16 18
39 42
50 55
93 99

出力例 3

Yes

Score : 550 points

Problem Statement

There are N squares arranged in a row, labeled 1, 2, \ldots, N from left to right.

You are given M pairs of integers (L_1, R_1), \ldots, (L_M, R_M).

A square j is defined to be bad if and only if there exists some i such that L_i \leq j \leq R_i.

Determine whether you can move from square 1 to square N by repeatedly performing the following action:

  • Let your current square be x. Choose an integer i that satisfies all of the following conditions, and move to square x + i.
    • A \leq i \leq B
    • x + i \leq N
    • Square x + i is not bad.

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M A B
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

If it is possible to reach square N by repeating the action described in the problem statement, print Yes. Otherwise, print No.

Sample Input 1

24 2 3 5
7 8
17 20

Sample Output 1

Yes

You can move to square N in this way: 1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24.

Sample Input 2

30 1 5 8
4 24

Sample Output 2

No

Sample Input 3

100 4 10 11
16 18
39 42
50 55
93 99

Sample Output 3

Yes