← 返回题目列表

AtCoder · awc0010_c

C. 山间小屋小径

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

分数: 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)满足以下两个条件的小屋编号:

  • 区间内所有相邻小屋之间都有一条小路。也就是说,对于所有整数 i 这样 l \leq i \leq r-1, |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 山间小屋属于一个区域。

高桥想回答 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
  • 第一行包含三个空格分隔的整数: N 代表山间小屋的数量, K 表示路径存在的最大高程差(当高程差最大时,路径存在 K),以及 Q 代表问题数量。
  • 第二行包含空格分隔的整数 A_1, A_2, \ldots, A_N 从左到右代表山间小屋的海拔。
  • 以下 Q 行每行包含一个问题。
  • 的 j- 这些行( (2 + j)-整个输入的第行)包含空格分隔的小屋编号 L_j 和 R_j 为 j- 第一个问题。

输出

输出 Q 行。上 j第行,打印 Yes 如果小屋 L_j 和小屋 R_j 属于同一区域 j第一个问题,以及 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