E - Checking Seats and Lunches Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は、ある学校の遠足の引率担当です。この遠足には N 台のバスが使われており、バス 1 からバス N まで番号が振られています。バス i には弁当が S_i 個積み込まれており、P_i 人の生徒が乗車しています。

昼食の時間になると、各バスに乗っている生徒全員に弁当を 1 人あたり 1 個ずつ配る必要があります。弁当はバス間で移動させることができないため、バス i で全員に弁当を配れる条件は S_i \geq P_i です。弁当が余る分には問題ありません。

遠足の計画では、M 件の休憩プランが提案されています。休憩プラン j では、バス L_j からバス R_j までの連続した番号のバスがまとめて休憩所に停車し、昼食をとります。

休憩プラン j が配布可能であるとは、L_j \leq i \leq R_j を満たすすべてのバス i について S_i \geq P_i が成り立つことをいいます。逆に、L_j \leq i \leq R_j を満たすバス i の中に S_i < P_i となるものが 1 台でも存在すれば、そのプランは配布不可です。

各休憩プランについて、配布可能かどうかを判定してください。

制約

  • 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
  • 1 行目には、バスの台数を表す整数 N と、休憩プランの数を表す整数 M が空白区切りで与えられる。
  • 2 行目には、各バスに積まれた弁当の個数 S_1, S_2, \ldots, S_N が空白区切りで与えられる。
  • 3 行目には、各バスに乗車している生徒の人数 P_1, P_2, \ldots, P_N が空白区切りで与えられる。
  • 続く M 行にわたって、各休憩プランの対象バスの区間が与えられる。
  • 3 + j 行目（ 1 \leq j \leq M ）では、休憩プラン j の区間の左端 L_j と右端 R_j が空白区切りで与えられる。

出力

M 行出力せよ。j 行目には、休憩プラン j が配布可能であれば Yes を、配布不可であれば 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

Score : 433 pts

Problem Statement

Takahashi is a chaperone for a school field trip. The field trip uses N buses, numbered from Bus 1 to Bus N. Bus i has S_i boxed lunches loaded on it, and P_i students are riding in it.

When lunchtime comes, each student on every bus must receive exactly 1 boxed lunch. Since boxed lunches cannot be transferred between buses, the condition for all students on Bus i to receive a lunch is S_i \geq P_i. Having leftover lunches is not a problem.

For the field trip plan, M rest stop plans have been proposed. In rest stop plan j, buses with consecutive numbers from Bus L_j to Bus R_j stop together at a rest area to have lunch.

Rest stop plan j is said to be distributable if S_i \geq P_i holds for every bus i satisfying L_j \leq i \leq R_j. Conversely, if there exists even one bus i with L_j \leq i \leq R_j such that S_i < P_i, the plan is not distributable.

For each rest stop plan, determine whether it is distributable or not.

Constraints

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

Input

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
  • The first line contains two integers separated by a space: N, the number of buses, and M, the number of rest stop plans.
  • The second line contains the number of boxed lunches loaded on each bus, S_1, S_2, \ldots, S_N, separated by spaces.
  • The third line contains the number of students riding each bus, P_1, P_2, \ldots, P_N, separated by spaces.
  • The following M lines give the bus range for each rest stop plan.
  • The (3 + j)-th line ( 1 \leq j \leq M ) contains the left endpoint L_j and right endpoint R_j of the range for rest stop plan j, separated by a space.

Output

Output M lines. On the j-th line, output Yes if rest stop plan j is distributable, or No if it is not distributable.

Sample Input 1

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

Sample Output 1

No
No
No

Sample Input 2

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

Sample Output 2

Yes
No
No
No
Yes

Sample Input 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

Sample Output 3

No
No
No
Yes
Yes
No
No
No