C - 山小屋の連絡路 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は山岳ガイドです。ある山岳地帯に N 個の山小屋が一列に並んでおり、左から i 番目の山小屋（以下、山小屋 i と呼びます）の標高は A_i メートルです。

隣接する山小屋の間には、標高差が小さい場合に限り連絡路が整備されています。具体的には、山小屋 i と山小屋 i+1 について、標高の差の絶対値が K 以下であるとき（すなわち |A_i - A_{i+1}| \leq K であるとき）、それらの山小屋の間には連絡路があり、直接行き来することができます。標高の差の絶対値が K より大きい場合、連絡路はなく、直接行き来することはできません。なお、隣接していない山小屋の間には連絡路はありません。

連絡路でつながった山小屋を順にたどることで互いに行き来できる山小屋の極大な集合を エリア と呼びます。連絡路は隣接する山小屋の間にしか存在しないため、各エリアに属する山小屋の番号は必ず連続した区間をなします。形式的には、エリアとは山小屋の番号の連続区間 [l, r]（1 \leq l \leq r \leq N）であって、以下の 2 つの条件をともに満たすもののことです。

  • 区間内のすべての隣接する山小屋間に連絡路がある。すなわち、l \leq i \leq r-1 なるすべての整数 i について |A_i - A_{i+1}| \leq K が成り立つ。（l = r の場合、この条件は自動的に満たされます。）
  • 区間は極大である。すなわち、l \geq 2 ならば |A_{l-1} - A_l| > K であり、r \leq N-1 ならば |A_r - A_{r+1}| > K である。

N 個の山小屋はそれぞれちょうど 1 つのエリアに属します。

高橋君は Q 個の質問に答えたいです。j 番目の質問では、山小屋 L_j と山小屋 R_j が同じエリアに属するかどうかを判定してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
  • 入力はすべて整数である。

入力

N K Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、山小屋の数を表す整数 N、連絡路が整備される標高差の上限を表す整数 K（標高差が K 以下のとき連絡路がある）、質問の数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、左から順に各山小屋の標高を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く Q 行にわたって、各質問が与えられる。
  • そのうち j 行目（入力全体の 2 + j 行目）では、j 番目の質問で対象となる山小屋の番号 L_j と R_j がスペース区切りで与えられる。

出力

Q 行出力せよ。j 行目には、j 番目の質問について、山小屋 L_j と山小屋 R_j が同じエリアに属するならば Yes を、そうでなければ No を出力せよ。

入力例 1

6 3 3
10 13 15 25 27 26
1 3
2 5
4 6

出力例 1

Yes
No
Yes

入力例 2

9 5 5
100 102 110 112 111 105 103 200 198
1 2
1 3
3 5
6 9
8 9

出力例 2

Yes
No
Yes
No
Yes

入力例 3

12 4 6
50 52 54 56 100 98 96 94 92 90 50 52
1 4
1 5
5 10
10 11
11 12
3 12

出力例 3

Yes
No
Yes
No
Yes
No

Score : 333 pts

Problem Statement

Takahashi is a mountain guide. In a certain mountainous region, N mountain huts are lined up in a row. The i-th mountain hut from the left (hereafter called hut i) is at an elevation of A_i meters.

Between adjacent mountain huts, trails are maintained only when the elevation difference is small. Specifically, for hut i and hut i+1, if the absolute difference in elevation is at most K (that is, |A_i - A_{i+1}| \leq K), there is a trail between them and one can travel directly between them. If the absolute difference in elevation is greater than K, there is no trail and one cannot travel directly between them. There are no trails between non-adjacent mountain huts.

A maximal set of mountain huts that can be reached from one another by following a sequence of trails is called an area. Since trails only exist between adjacent huts, the hut numbers belonging to each area always form a contiguous interval. Formally, an area is a contiguous interval [l, r] (1 \leq l \leq r \leq N) of hut numbers that satisfies both of the following conditions:

  • There is a trail between all adjacent huts within the interval. That is, for all integers i such that l \leq i \leq r-1, |A_i - A_{i+1}| \leq K holds. (When l = r, this condition is automatically satisfied.)
  • The interval is maximal. That is, if l \geq 2 then |A_{l-1} - A_l| > K, and if r \leq N-1 then |A_r - A_{r+1}| > K.

Each of the N mountain huts belongs to exactly one area.

Takahashi wants to answer Q questions. For the j-th question, determine whether hut L_j and hut R_j belong to the same area.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
  • All input values are integers.

Input

N K Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains three space-separated integers: N representing the number of mountain huts, K representing the maximum elevation difference for a trail to exist (a trail exists when the elevation difference is at most K), and Q representing the number of questions.
  • The second line contains space-separated integers A_1, A_2, \ldots, A_N representing the elevations of the mountain huts from left to right.
  • The following Q lines each contain a question.
  • The j-th of these lines (the (2 + j)-th line of the entire input) contains space-separated hut numbers L_j and R_j for the j-th question.

Output

Output Q lines. On the j-th line, print Yes if hut L_j and hut R_j belong to the same area for the j-th question, and No otherwise.

Sample Input 1

6 3 3
10 13 15 25 27 26
1 3
2 5
4 6

Sample Output 1

Yes
No
Yes

Sample Input 2

9 5 5
100 102 110 112 111 105 103 200 198
1 2
1 3
3 5
6 9
8 9

Sample Output 2

Yes
No
Yes
No
Yes

Sample Input 3

12 4 6
50 52 54 56 100 98 96 94 92 90 50 52
1 4
1 5
5 10
10 11
11 12
3 12

Sample Output 3

Yes
No
Yes
No
Yes
No