codeforces#P1548E. Gregor and the Two Painters
Gregor and the Two Painters
Description
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.
Input
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.
Output
Print a single integer, the number of badly painted regions.
Samples
3 4 11
9 8 5
10 6 7 2
2
3 4 12
9 8 5
10 6 7 2
1
3 3 2
1 2 1
1 2 1
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
6
Note
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.
