← 返回题目列表

AtCoder · abc391_d

G. 重力

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

分数: 400 点

问题陈述

有一个网格 10^9 行和 W 列。牢房位于 x从左边算起第 y从第 底部 表示为 (x,y).

有 N 块。每个块都是一个 1 \times 1 方形、块状 i-th (1 \leq i \leq N) 位于单元格 (X_i,Y_i) 时间 0.

有时 t=1,2,\dots,10^{100},块根据以下规则移动:

  • 如果整个底部行都充满了块,则底部行中的所有块都将被删除。
  • 对于每个剩余块,按从下到上的顺序执行以下操作:
    • 如果该块位于底行,或者如果紧邻其下方的单元格中有一个块,则不执行任何操作。
    • 否则,将该块向下移动一个单元格。

你被给予 Q 查询。对于 j- 第一个查询 (1 \leq j \leq Q),回答是否阻塞 A_j 存在于时间 T_j+0.5.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq N
  • 1 \leq X_i \leq W
  • 1 \leq Y_i \leq 10^9
  • (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq T_j \leq 10^9
  • 1 \leq A_j \leq N
  • 所有输入值均为整数。

输入

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

N W
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
Q
T_1 A_1
T_2 A_2
\vdots
T_Q A_Q

输出

打印 您选择的 Q 行。的 i- 第行应包含 Yes if 块 A_i 存在于时间 T_i+0.5,和 No 否则。


示例输入 1

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

示例输出 1

Yes
Yes
No
Yes
No
Yes

块的位置变化如下:(“时刻”表示“时间”。)

  • 查询 1: 在时间 1.5,块 1 存在,所以答案是 Yes.
  • 查询 2: 在时间 1.5,块 2 存在,所以答案是 Yes.
  • 查询 3:块 3 消失的时间 2,所以它当时不存在 2.5,答案是 No.

示例输入 2

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

示例输出 2

No
No
Yes
Yes