← 返回题目列表

Codeforces · 1392/I

I. 凯文和网格

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

当凯文在 BigMan 的房子里时,突然一个陷阱把他送到了一个有 $$$n$$$ 行和 $$$m$$$ 列的网格上。

BigMan 的陷阱由两个数组配置:数组 $$$a_1,a_2,\ldots,a_n$$$ 和数组 $$$b_1,b_2,\ldots,b_m$$$。

在第 $$$i$$$ 行中有一个加热器,该加热器将该行加热 $$$a_i$$$ 度,在第 $$$j$$$ 列中有一个加热器将该列加热 $$$b_j$$$ 度,因此单元 $$$(i,j)$$$ 的温度为 $$$a_i+b_j$$$。

幸运的是,Kevin 有一套带有一个参数 $$$x$$$ 和两种模式的套装:

- 耐热性。在此模式下,套装可以承受所有大于或等于 $$$x$$$ 的温度,但一旦到达温度低于 $$$x$$$ 的单元格就会冻结。
- 耐寒性。在此模式下,套装可以承受低于 $$$x$$$ 的所有温度,但一旦到达温度至少为 $$$x$$$ 的单元格就会燃烧。

一旦凯文降落在一个单元上,如果单元的温度低于$$$x$$$,套装会自动转为耐寒模式,否则转为耐热模式,并且此后无法更改。

如果两个单元共享一条边,我们就说它们是相邻的。

令路径为单元格序列 $$$c_1,c_2,\ldots,c_k$$$,使得 $$$c_i$$$ 和 $$$c_{i+1}$$$ 相邻 $$$1 \leq i \leq k-1$$$。

如果两个单元格之间存在一条仅由 Kevin 可以踩到的单元格组成的路径,我们就说两个单元格是相连的。

连接分量是成对连接单元的最大集合。

如果 Kevin 能够从它开始逃离网格(当它至少包含一个网格边界单元时),我们就说一个连通分量是好的,否则它就是坏的。

为了评估情况,Kevin 给每个好的组件打了 $$$1$$$ 的分数,给每个坏的组件打了 $$$2$$$ 的分数。

最终得分将是温度大于或等于$$$x$$$的组件的总分与温度小于$$$x$$$的组件的得分之差。

Kevin 可以使用 $$$q$$$ 个可能的 $$$x$$$ 值,对于每个值,Kevin 想知道最终得分。

帮助凯文击败BigMan!

输入

第一行包含三个整数 $$$n$$$,$$$m$$$,$$$q$$$ ($$$1 \leq n,m,q \leq 10^5$$$) – 分别是行数、列数以及 $$x$$$ 的可能值数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$)。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \leq b_i \leq 10^5$$$)。

接下来的每一行 $$$q$$$ 都包含一个整数 $$$x$$$ ($$$1 \leq x \leq 2 \cdot 10^5$$$)。

输出

输出 $$$q$$$ 行,在第 $$$i$$$ 行中输出输入中 $$$x$$$ 的第 $$$i$$$ 可能值的答案。

示例

输入 #1

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

输出 #1

-1

输入 #2

3 3 2
1 2 2
2 1 2
3
4

输出 #2

0
1

注意

在第一个示例中,温度小于 $$$5$$$ 的组件的得分为 $$$1+2$​​$$,温度至少为 $$$5$$$ 的组件的得分为 $$$2$$$。因此,最终得分为$$$2-3=-1$$$。