← 返回题目列表

Codeforces · 1548/E

E. 格雷戈尔和两个画家

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

两位画家,阿明和本杰,正在重新粉刷格雷戈尔的客厅天花板!天花板可以建​​模为 $$$n \times m$$$ 网格。

对于 $$$1$$$ 和 $$$n$$$(含)之间的每个 $$$i$$$,画家 Amin 将 $$$a_i$$$ 层涂料应用于整个第 $$$i$$$ 行。对于 $$$1$$$ 和 $$$m$$$(含)之间的每个 $$$j$$$,画家 Benj 将 $$$b_j$$$ 层涂料应用于整个 $$$j$$$ 列。因此,单元格 $$$(i,j)$$$ 最终会涂上 $$$a_i+b_j$$$ 层油漆。

如果 $$$a_i+b_j \le x$$$,Gregor 认为单元格 $$$(i,j)$$$ 绘制得很糟糕。将绘制错误的区域定义为绘制错误的单元的最大连通分量,即。 e.由涂得不好的单元组成的连接组件,使得与该组件单元相邻的所有单元都不会涂得不好。如果两个单元共用一条边,则认为它们是相邻的。

Gregor 对完成的天花板的状态感到震惊,并想知道涂漆不良区域的数量。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$x$$$ ($$$1 \le n,m \le 2\cdot 10^5$$$, $$$1 \le x \le 2\cdot 10^5$$$) — Gregor 天花板的尺寸,以及涂漆不良的单元格中油漆层的最大数量。

第二行包含$$$n$$$整数$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot 10^5$$$),每行应用的油漆层数Amin。

第三行包含$$$m$$$整数$$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_j \le 2\cdot 10^5$$$),Benj应用于每列的油漆层数。

输出

打印一个整数,即绘制得不好的区域的数量。

示例

输入 #1

3 4 11
9 8 5
10 6 7 2

输出 #1

2

输入 #2

3 4 12
9 8 5
10 6 7 2

输出 #2

1

输入 #3

3 3 2
1 2 1
1 2 1

输出 #3

4

输入#4

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

输出#4

6

注意

下图表示第一个示例。每行左边的数字代表列表$$$a$$$,每列上方的数字代表列表$$$b$$$。每个单元格内的数字代表该单元格中油漆层的数量。

彩色单元格对应于涂色不良的单元格。红色和蓝色单元格分别形成$$$2$$$ 绘制得很糟糕的区域。