Gregor and the Two Painters

题意翻译

给定两个长度分别为 $n,m$ 的序列 $a,b$ 和一个参数 $x$ 生成一个 $n\times m$ 的黑白矩阵，$(i,j)$ 为黑当且仅当 $a_i+b_j\leq x$ 求矩阵内黑色四连通块数 $n,m,a_i,b_i\leq 2\times 10^5$

题目描述

Two painters, Amin and Benj, are repainting Gregor's living room ceiling! The ceiling can be modeled as an $ n \times m $ grid. For each $ i $ between $ 1 $ and $ n $ , inclusive, painter Amin applies $ a_i $ layers of paint to the entire $ i $ -th row. For each $ j $ between $ 1 $ and $ m $ , inclusive, painter Benj applies $ b_j $ layers of paint to the entire $ j $ -th column. Therefore, the cell $ (i,j) $ ends up with $ a_i+b_j $ layers of paint. Gregor considers the cell $ (i,j) $ to be badly painted if $ a_i+b_j \le x $ . Define a badly painted region to be a maximal connected component of badly painted cells, i. e. a connected component of badly painted cells such that all adjacent to the component cells are not badly painted. Two cells are considered adjacent if they share a side. Gregor is appalled by the state of the finished ceiling, and wants to know the number of badly painted regions.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ x $ ( $ 1 \le n,m \le 2\cdot 10^5 $ , $ 1 \le x \le 2\cdot 10^5 $ ) — the dimensions of Gregor's ceiling, and the maximum number of paint layers in a badly painted cell. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 2\cdot 10^5 $ ), the number of paint layers Amin applies to each row. The third line contains $ m $ integers $ b_1, b_2, \ldots, b_m $ ( $ 1 \le b_j \le 2\cdot 10^5 $ ), the number of paint layers Benj applies to each column.

输出格式

Print a single integer, the number of badly painted regions.

输入输出样例

输入样例 #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

说明

The diagram below represents the first example. The numbers to the left of each row represent the list $ a $ , and the numbers above each column represent the list $ b $ . The numbers inside each cell represent the number of paint layers in that cell. The colored cells correspond to badly painted cells. The red and blue cells respectively form $ 2 $ badly painted regions. 

题意翻译

给定两个长度分别为 $n,m$ 的序列 $a,b$ 和一个参数 $x$ 生成一个 $n\times m$ 的黑白矩阵，$(i,j)$ 为黑当且仅当 $a_i+b_j\leq x$ 求矩阵内黑色四连通块数 $n,m,a_i,b_i\leq 2\times 10^5$