← 返回题目列表

AtCoder · arc196_d

D. 道路

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

分数: 900 点

问题陈述

有 N 城镇,编号 1,2,\ldots,N,按此顺序排成一行。

有 N-1 连接相邻城镇的道路:道路 j\,(1 \leq j \leq N-1) 连接城镇 j 和 j+1。对于每条道路 j,您可以设置 实力 w_j (可以是负数的整数)。

当一个人沿着道路行驶时,他们的 耐力 变化。具体来说,如果一个人有耐力 x 沿着道路行驶 j,他们的耐力变成 x + w_j.

有 M 现在将在这些城镇之间移动的人。

人 i\,(1 \le i \le M) 从耐力开始 0 在镇上 S_i 并前往城镇 T_i 通过最短路径。 可以保证 |S_i - T_i| > 1。另外, (S_i, T_i) \neq (S_j, T_j) if i \neq j.

人 i的要求如下:

离开城镇时 S_i 以及到达城镇时 T_i,他们的体力应该正好是 0。在其他每个城镇,他们的体力应该始终是正整数。

假设除了上述沿道路行驶造成的耐力变化外,耐力没有任何变化。

流程 Q 查询。对于 k第一个查询 (1 \le k \le Q),如果可以设置强项道路,使得所有人的要求 L_k, L_k + 1, \ldots, R_k 满意,打印 Yes;否则,打印 No.

约束

  • 3 \le N \le 4 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 1 \le S_i, T_i \le N
  • |S_i - T_i| > 1
  • (S_i, T_i) \neq (S_j, T_j)\,(i \neq j)
  • 1 \le L_k \le R_k \le M
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M Q
S_1 T_1
S_2 T_2
\vdots
S_M T_M
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

输出

打印 Q 行。

的 k- 第行应包含 Yes 是否有一种方法可以设置强项道路以便满足所有人的要求 L_k, L_k + 1, \ldots, R_k 满意,并且 No 否则。


示例输入 1

5 4 2
4 2
1 3
3 5
2 4
1 3
2 4

示例输出 1

Yes
No

对于第一个查询,考虑设置道路的强度 1, 2, 3, 4 to 1, -1, 1, -1。

  • 人 1 从城镇开始 4 有耐力 0,访问城镇 3 有耐力 1,到达城镇 2 有耐力 0.
  • 人 2 从城镇开始 1 有耐力 0,访问城镇 2 有耐力 1,到达城镇 3 有耐力 0.
  • 人 3 从城镇开始 3 有耐力 0,访问城镇 4 有耐力 1,到达城镇 5 有耐力 0.

因此,这种配置满足了人们的要求 1,2,3,所以打印 Yes 在第一行。

对于第二个查询,无法满足人员的要求 2,3,4 同时,所以打印 No.


示例输入 2

7 6 3
1 5
2 4
4 6
7 1
5 3
1 6
1 6
4 4
2 5

示例输出 2

No
Yes
Yes