CF1548E Gregor and the Two Painters

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.

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.