← 返回题目列表

AtCoder · pakencamp_2025_day2_e

E. 大帕肯

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

配点 : 100 点

問題文

Grand Paken是位于Paken王国一角的建筑。 H 行、横 W 它具有矩形形状,内部有一个柱子。 它分为 1 \times 1 方形部分。从上面 a 列,从左起 b 划分列部分 它被称为 (a,b) 。位于大帕肯 有 N 出口,i 第二个出口是一段 位于 (A_{i},B_{i}) 。


一个阳光明媚的日子,Grand Phakeng 发生火灾。 火灾的根源是 M 有些地方,i 来源是 (C_i,D_i) 。所有火灾开始于 与 0 同时发生。 火是单位时间 1 垂直和水平传播到相邻部分。隔间 (x,y) 是时间 当 t 至 该值是 燃烧 表示曼哈顿距某个火源的距离为 t 或更少。此外,一旦某个部分开始燃烧,它将继续燃烧。


你作为救援队被派遣,必须执行以下操作来帮助困在建筑物内的人们。 Q 疑问需要得到解答。 对于第 i 个查询,请考虑以下情况。

  • 時刻 0 ,人们是分裂的 (X_{i},Y_{i}) 。
  • 人是一个时间单位 1 您可以垂直和水平移动到相邻部分。
  • 只有在逗留期间情节尚未着火的情况下,一个人才能采取行动。

换句话说,时间 为了达到 t ,该部分开始燃烧的时间必须是 t 必须严格大于。在这些条件下,确定人员是否可以通过任一出口到达车厢。如果可以到达 Yes,如果不可能 No 。

制約

  • 1 \le H, W \le 2 \times 10^5
  • 1 \le N, M, Q \le 2 \times 10^5
  • 1 \le A_i \le H
  • 1 \le B_i \le W
  • 1 \le C_i \le H
  • 1 \le D_i \le W
  • 1 \le X_i \le H
  • 1 \le Y_i \le W
  • 所有输入均为整数

小課題

  1. (10 点) H \times W \leq 300
  2. (20 点) H,W \leq 300
  3. (30 点) H,W \leq 2000
  4. (40 点)无附加约束 打印第

入力

输入是按以下格式从标准输入给出的。

H W
N
A_1 B_1
\vdots
A_N B_N
M
C_1 D_1
\vdots
C_M D_M
Q
X_1 Y_1
\vdots
X_Q Y_Q

出力

Q 行。i 行中,i 个查询的答案。


入力例 1

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

出力例 1

No
No
Yes

1,2 关于第二个查询,无论怎么移动,在满足条件的情况下都无法移动。

3 对于第二个查询,人们 我在 0 至 该值是 (1,5) 。时间 通过移动到 1 至 该值是 (2,5) ,满足条件即可移动。 它从(2,5) 是时间 它以 3 开始燃烧。