A6888 · Rorororobot · GESP考级

题目描述

有一个 $n$ 行 $m$ 列的网格，行从下往上从 $1$ 到 $n$ 编号，列从左往右从 $1$ 到 $m$ 编号。第 $i$ 列的最底下 $a_i$ 个格子（第 $1,2,\cdots,a_i$ 行的格子）被封锁了，其余的 $n-a_i$ 个格子没有被封锁。 一个机器人在穿越这片网格。你可以向它发送指令——向上，向右，向下或向左。如果机器人尝试走进被封锁的格子或离开网格，它将爆炸。 然而，这个机器人是坏掉的——它会执行每个它收到的指令 $k$ 次。所以如果你让它向上，它将会向上移动 $k$ 次（$k$ 个格子）。你不能在机器人正在执行一个指令的时候发送另一个指令。 给你 $q$ 个关于机器人的询问。每个询问有一个起始格子，终止格子和一个数值 $k$。问在机器人执行每一个指令 $k$ 次时，能否向它发送若干个指令（可能为零），使其从起始格子出发到达终止格子？ 机器人必须在终止格子中停下。在执行指令的过程中经过终止格子是不作数的。

第一行两个整数 $n,m(1\le n\le 10^9,1\le m\le 2\times 10^5)$，表示网格的行数和列数。 第二行 $m$ 个整数 $a_1,a_2,\cdots,a_m(0\le a_i\le n)$，表示第 $i$ 列底部被封锁的格子数。 第三行一个整数 $q(1\le q\le 2\times 10^5)$，表示询问的个数。 接下来 $q$ 行，每行五个整数 $x_s,y_s,x_f,y_f,k(a[y_s]<x_s\le n,1\le y_s\le m,a[y_f]<x_f\le n,1\le y_f\le m,1\le k\le 10^9)$，分别表示起始格子所在行和列，终止格子所在行和列，以及每个指令被重复执行的次数。每个询问的起始格子和终止格子都是未被封锁的。

对于每个询问，输出一行一个字符串，如果在机器人执行每个指令 $k$ 次时可以通过若干个（可能为零）指令让机器人从起始格子出发到达终止格子，输出 YES ；否则输出 NO 。

输入 #1

11 10
9 0 0 10 3 4 8 11 10 8
6
1 2 1 3 1
1 2 1 3 2
4 3 4 5 2
5 3 11 5 3
5 3 11 5 2
11 9 9 10 1

输出 #1

YES
NO
NO
NO
YES
YES