← 返回题目列表

Codeforces · 2044/F

F. 简单的恶魔问题

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

对于任意网格,Robot 将其美感定义为网格中元素的总和。

Robot 给你一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个长度为 $$$m$$$ 的数组 $$$b$$$。您通过 $$$m$$$ 网格 $$$M$$$ 构建 $$$n$$$,使得 $$$M_{i,j}=a_i\cdot b_j$$$ 对于所有 $$$1 \leq i \leq n$$$ 和 $$$1 \leq j \leq m$$$。

然后,Robot 会为您提供 $$$q$$$ 查询,每个查询由一个整数 $$$x$$$ 组成。对于每个查询,确定是否可以仅执行一次以下操作,以便 $$$M$$$ 具有 $$$x$$$ 的美感:

1. 选择整数 $$$r$$$ 和 $$$c$$$ 使得 $$$1 \leq r \leq n$$$ 和 $$$1 \leq c \leq m$$$
2. 对于所有有序对 $$$(i,j)$$$,将 $$$M_{i,j}$$$ 设置为 $$$0$$$,使得 $$$i=r$$$、$$$j=c$$$ 或两者。

请注意,查询不是持久性的,这意味着您在此过程中实际上并未将任何元素设置为 $$$0$$$ — 仅需要输出是否可以找到 $$$r$$$ 和 $$$c$$$ ,这样如果执行上述操作,网格的美观度将是 $$$x$$$。另外,请注意,您必须为每个查询执行该操作,即使原始网格的美观度已经是$$$x$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \leq n,m \leq 2\cdot 10^5, 1 \leq q \leq 5\cdot 10^4$$$) — $$$a$$$ 的长度、$$$b$$$ 的长度和数量分别查询。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq |a_i| \leq n$$$)。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq |b_i| \leq m$$$)。

下面的 $$$q$$$ 行每行包含一个整数 $$$x$$$ ($$$1 \leq |x| \leq 2\cdot 10^5$$$),您希望通过将行和列中的所有元素设置为 $$$0$$$ 来实现网格的美观。

输出

对于每个测试用例,如果有办法执行上述操作,使得美丽为 $$$x$$$,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yES”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

3 3 6
-2 3 -3
-2 2 -1
-1
1
-2
2
-3
3

输出 #1

NO
YES
NO
NO
YES
NO

输入 #2

5 5 6
1 -2 3 0 0
0 -2 5 0 -3
4
-3
5
2
-1
2

输出 #2

YES
YES
YES
YES
NO
YES

注意

在第二个示例中,网格是

0 -2 5 0 -3

0 4 -10 0 6

0 -6 15 0 -9

0 0 0 0 0

0 0 0 0 0

通过执行 $$$r=4$$$ 和 $$$c=2$$$ 的操作,我们创建以下网格:

0 0 5 0 -3

0 0 -10 0 6

0 0 15 0 -9

0 0 0 0 0

0 0 0 0 0

美丽$$$4$$$。因此,我们输出 YES。

在第二个查询中,选择 $$$r=3$$$ 和 $$$c=5$$$ 创建一个具有美丽 $$$-3$$$ 的网格。

在第三个查询中,选择 $$$r=3$$$ 和 $$$c=3$$$ 创建一个具有美丽 $$$5$$$ 的网格。