分数: 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