407304: GYM102759 B Cactus Competition

In Byteland, there is a school with an enormously large playground. The playground is an $$$N \times M$$$ grid. Since the playground is so large, the weather may differ in different squares of the grid. For $$$1 \le i \le N, 1 \le j \le M$$$, cell $$$(i, j)$$$ has a temperature of $$$A_i + B_j$$$. The sequences $$$A$$$ and $$$B$$$ are known in advance.

Sunghyeon wants to organize a relay race competition in the playground. The race will start in cell $$$(S, 1)$$$ and end in cell $$$(T, M)$$$, where $$$S$$$ and $$$T$$$ are integers that are to be determined. In the race, students will only run to the right and down. In other words, a student in cell $$$(i, j)$$$ can move directly to cells $$$(i, j + 1)$$$ or $$$(i + 1, j)$$$. From this, it is clear that $$$1 \le S \le T \le N$$$ must hold for the race to be valid.

The people of Byteland love cacti. Therefore, all students will hold a cactus while in the race. Since cacti can't endure cold weather, all cells in the racetrack should satisfy $$$A_i + B_j \geq 0$$$.

There are $$$\frac{N(N+1)}{2}$$$ candidate races over all candidate pairs of $$$S$$$ and $$$T$$$. Please find the number of valid pairs - a pair is valid if the corresponding race can be completed given the constraints due to the cacti.

The first line contains two space-separated integers $$$N, M$$$ ($$$1 \le N, M \le 200\,000$$$).

The second line contains $$$N$$$ space-separated integers $$$A_1,A_2, \cdots, A_N$$$ ($$$-10^9 \le A_i \le 10^9$$$).

The third and final line contains $$$M$$$ space-separated integers $$$B_1,B_2, \cdots, B_M$$$ ($$$-10^9 \le B_i \le 10^9$$$).

Print the number of valid pairs of $$$S$$$ and $$$T$$$.

3 3
-1 0 1
-1 0 1

1

3 3
-1 0 1
1 0 1

5