← 返回题目列表

AtCoder · awc0022_c

C. 道路坑洼调查

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

分数: 333 分

问题陈述

高桥在市政府道路管理科工作。其管辖范围内的路面包括 N 瓷砖排列成行,编号瓷砖 1, 2, \ldots, N 从左到右。

其中, M 瓷砖损坏。损坏瓷砖的数量为 B_1, B_2, \ldots, B_M,所有这些都是不同的(不一定按升序排列)。

有一天, K 汽车沿着这条路行驶。的 i第车(1 \leq i \leq K) 在tile的连续部分中精确地传递每个tile一次 L_i 平铺 R_i (L_i \leq R_i)。每辆汽车的行驶不会影响其他汽车的行驶,并且当汽车经过时,瓷砖不会改变其状态。

每次汽车经过一块损坏的瓷砖时,都会发生一次震动。即,所产生的冲击总数 i第辆车的行程等于瓷砖部分中包含的损坏瓷砖的数量 L_i 平铺 R_i.

对于每辆车,Takahashi 计算其行驶过程中产生的震动总数,并且是否至少达到阈值 T,他报告汽车的行驶部分“需要修理”。在这里, T 作为正整数给出。

对于每个 K 汽车,确定其行驶部分是否报告为需要维修。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq N
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq T \leq N
  • 1 \leq B_i \leq N (1 \leq i \leq M)
  • 全部 B_i 是不同的
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq K)
  • 所有输入值均为整数

输入

N M K T
B_1 B_2 \ldots B_M
L_1 R_1
L_2 R_2
\vdots
L_K R_K
  • 第一行包含瓷砖总数 N,损坏的瓷砖数量 M,汽车数量 K,以及冲击计数阈值 T,用空格分隔。
  • 第二行包含损坏瓷砖的数量 B_1, B_2, \ldots, B_M,用空格分隔。它们不一定按升序排列。
  • 以下 K 行给出了每辆车的行驶路段。
  • 的 (2 + i)第行包含左端点 L_i 和右端点 R_i 的 i第辆车的行驶部分,以空格分隔。

输出

输出 K 行。上 i第行,打印 YES 如果 i第辆车的行驶部分报告需要维修,并且 NO 否则。


示例输入 1

10 3 3 2
2 5 8
1 6
3 4
4 9

示例输出 1

YES
NO
YES

示例输入 2

5 1 3 2
3
1 2
3 3
1 5

示例输出 2

NO
NO
NO

示例输入 3

20 6 8 3
3 7 10 12 15 18
1 20
1 5
5 15
10 18
1 2
14 16
6 13
11 14

示例输出 3

YES
NO
YES
YES
NO
NO
YES
NO

示例输入 4

50 10 12 4
31 5 44 17 28 12 49 36 23 40
1 50
1 10
10 30
20 45
1 4
5 5
30 50
15 25
35 50
1 28
43 46
25 42

示例输出 4

YES
NO
YES
YES
NO
NO
YES
NO
YES
YES
NO
YES

示例输入 5

1 1 1 1
1
1 1

示例输出 5

YES