← 返回题目列表

AtCoder · awc0072_e

E. 检查座位和午餐

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

分数: 433 分

问题陈述

高桥是学校实地考察的陪同人员。实地考察使用 N 巴士,编号自 Bus 1 转 巴士 N。巴士 i 有 S_i 盒装午餐装在上面,并且 P_i 学生正在里面骑。

午餐时间到来时,每辆巴士上的每个学生都必须收到准确的 1 盒饭。由于盒装午餐不能在巴士之间转移,所有乘坐巴士的学生的条件 i 收到午餐的是 S_i \geq P_i。吃剩下的午餐不是问题。

对于实地考察计划, M 休息站计划已提出。休息站计划中 j,Bus 中连续编号的公交车 L_j 转 巴士 R_j 一起在休息区停下来吃午饭。

休息站计划 j 据说是 可分发 if S_i \geq P_i 适用于每辆巴士 i 满意 L_j \leq i \leq R_j。相反,如果存在哪怕一辆公共汽车 i 与 L_j \leq i \leq R_j 这样 S_i < P_i,计划是 不可分发.

对于每个休息站计划,确定其是否可分发。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 ( 1 \leq i \leq N )
  • 0 \leq P_i \leq 10^9 ( 1 \leq i \leq N )
  • 1 \leq L_j \leq R_j \leq N ( 1 \leq j \leq M )
  • 所有输入值均为整数。

输入

N M
S_1 S_2 \ldots S_N
P_1 P_2 \ldots P_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 第一行包含两个用空格分隔的整数: N,公交车数量,以及 M,休息站计划数。
  • 第二行包含每辆公交车装载的盒饭数量, S_1, S_2, \ldots, S_N,用空格分隔。
  • 第三行包含每辆公交车乘坐的学生人数, P_1, P_2, \ldots, P_N,用空格分隔。
  • 以下 M 行给出了每个休息站计划的巴士范围。
  • 的 (3 + j)- 第行 ( 1 \leq j \leq M ) 包含左端点 L_j 和右端点 休息停止计划范围的 R_j 休息站计划的范围 j,用空格分隔。

输出

输出 M 行。上 j第行,输出 Yes 如果休息停止计划 j 是可分发的,或者 No 如果它不可分发。


示例输入 1

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

示例输出 1

No
No
No

示例输入 2

4 5
5 0 3 10
5 1 3 10
1 1
1 4
2 2
2 3
4 4

示例输出 2

Yes
No
No
No
Yes

示例输入 3

10 8
100 50 30 20 60 10 45 80 25 70
90 50 35 15 60 10 40 85 20 65
1 10
1 5
3 3
4 6
6 6
7 9
5 8
1 3

示例输出 3

No
No
No
Yes
Yes
No
No
No