Gregor and the Two Painters
Contest: Codeforces Round 736 (Div. 1)
Difficulty rating: 3400
Tags: data structures, divide and conquer, graphs, greedy, math

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.

Input format:
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 format:
Print a single integer, the number of badly painted regions.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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.

Example input:
3 4 11
9 8 5
10 6 7 2

Example output:
2

Example input:
3 4 12
9 8 5
10 6 7 2

Example output:
1

Editorial:
Inspired by a previous CF task.
For simplicity let's assume that all $$$a_i$$$ are distinct (and similarly, all $$$b_j$$$). If this is not the case, we may break ties arbitrarily.
Say that two badly painted cells are directly reachable from each other if they are in the same row or column and all cells in between them are also badly painted. Also, define the value of the cell at $$$(i,j)$$$ to be $$$a_i+b_j$$$. Call a badly painted cell a representative if no cell directly reachable from it has a smaller value than it.
Claim: Every connected component of badly painted cells contains exactly one representative.
Proof: Clearly every connected component contains at least one representative; consider the cell(s) with the minimum value contained within it. To show that every connected component contains exactly one representative, suppose that we are given a representative $$$(i,j)$$$ that is directly reachable from $$$(i',j)$$$ for all $$$i_l\le i'\le i_r$$$ and $$$(i,j')$$$ for all $$$j_l\le j'\le j_r$$$, where $$$a_i=\min_{i_l\le i'\le i_r}(a_{i'})$$$ and $$$b_j=\min_{j_l\le j'\le j_r}(b_{j'})$$$. Then the connected component containing $$$(i,j)$$$ is completely contained within the rectangle $$$[i_l,i_r]\times [j_l,j_r]$$$, and $$$(i,j)$$$ is the unique cell with the minimum value within that rectangle. This implies that a representative is always the unique cell with the minimum value within its connected component.
It remains to count the number of representatives. For each $$$i$$$, let $$$lo_i$$$ be the maximum index less than $$$hi_i$$$ such that $$$a_{lo_i}<a_i$$$ and $$$hi_i$$$ be the minimum index greater than $$$i$$$ such that $$$a_{hi_i}<a_i$$$. Then define $$$na_i$$$ to be $$$\min(\max_{i'\in [lo_i,i]}a_{i'},\max_{i'\in [i,hi_i]}a_{i'})$$$. Any path from a cell in row $$$i$$$ to a cell in the same column with lower value must pass through a row with value at least $$$na_i$$$. Define $$$nb_j$$$ for each $$$j$$$ similarly. I claim that $$$(i,j)$$$ is a representative if and only if the following three conditions hold:
1. $$$a_i+b_j\le X$$$
2. $$$na_i+b_j>X$$$
3. $$$b_i+nb_j>X$$$
Computing $$$na$$$ and $$$nb$$$ can be done in $$$O(N\log N+M\log M)$$$ with any data structure supporting range min/max queries (e.g. sparse tables) or in $$$O(N+M)$$$ with a stack.
It remains to count the number of pairs $$$(i,j)$$$ that satisfy these conditions given $$$a$$$, $$$na$$$, $$$b$$$, and $$$nb$$$. First initialize two binary indexed trees $$$T_a$$$ and $$$T_b$$$. Then sort the pairs $$$(na_i-a_i,a_i),(nb_j-b_j,b_j)$$$ in decreasing order. Now for every pair in the order, if it is of the form $$$(na_i-a_i,a_i)$$$, then add to the answer the number of elements of $$$T_b$$$ that are in the range $$$(X-na_i,X-a_i]$$$, and add $$$a_i$$$ to $$$T_a$$$. The reasoning for the case $$$(nb_j-b_j,b_j)$$$ is similar (query $$$T_a$$$, update $$$T_b$$$).