An Animal Contest 3 P4 - Monkey Mayhem

View as PDF

Submit solution


Points: 7
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

William the monkey finds himself in a bar! Immediately upon entering the bar William notices that something isn't right. All the monkeys in the bar are under a spell! William decides to split the bar into a grid of (N+1) rows and (M+1) columns — the rows are numbered 0 through N and the columns are numbered 0 through M. In this bar, William counts N+M monkeys. There are N monkeys located at the beginning of the rows, with each row i from 1 to N containing one monkey at cell (i,0). Similarly, there are M monkeys located at the top of the columns, with each column j from 1 to M containing one monkey at cell (0,j).

So far the monkeys haven't moved, but they will soon! Since William can read minds, he knows exactly when each monkey will start moving forward. It's also possible that a monkey is so spellbound that it won't move at all! After a monkey starts moving, it continues moving at exactly one cell per second, only stopping when it leaves the grid. The monkeys at the beginning of the rows move horizontally to the right and the monkeys at the top of the columns move vertically downwards.

Given William's information, he wants to know the number of collisions that will occur between any two monkeys because he is a sadistic monkey and enjoys watching monkeys crash into each other. Note that a collision is when two monkeys arrive at the same cell at the same time. After a collision occurs, both monkeys are awakened from the spell and go home, meaning they can no longer be part of any further collisions.

If a monkey starts at the topmost row and starts moving at time x, it will arrive at row r at time x+r. Similarly, if a monkey starts at the leftmost column and starts moving at time x, it will arrive at column c at time x+c.

Constraints

1 \le N, M \le 5 \times 10^5

-1 \le a_i, b_i \le 10^9

Input Specification

The first line contains N and M.

The next line contains N space-separated integers a_i, with the i^{th} integer representing the time at which the monkey on the i^{th} row starts moving. If a_i is -1, the monkey will not move.

The next and final line contains M space-separated integers b_i, with the i^{th} integer representing the time at which the monkey on the i^{th} column starts moving. If b_i is -1, the monkey will not move.

Output Specification

Output one integer representing the total number of collisions that will occur.

Sample Input 1

1 2
0
0 1

Sample Output 1

1

Explanation for Sample 1

For the purposes of this explanation, assume that in the above diagrams, cell (0, 0) is the top-leftmost cell and cell (N, M) is the bottom-rightmost cell. A and B represent the monkeys starting on the top row and 1 represents the monkey starting at the leftmost column.

The initial configuration at time 0 and direction of movement for each monkey is shown by the leftmost diagram, with each subsequent diagram representing the configuration at times 1, 2, and 3.

At time 1 monkeys A and 1, having departed at time 0, both arrive at cell (1, 1) and crash into each other. They both leave the bar immediately. Monkey B departs.

At time 2 monkey B arrives at cell (1, 2) and does not crash into monkey 1 — monkey 1 was already taken out by monkey A earlier.

At time 3 monkey B exits the bar and our simulation is complete. We can see that 1 collision occurred.

Sample Input 2

6 9
7 27 0 4 20 -1
-1 -1 9 -1 22 31 1 0 24

Sample Output 2

3

Comments

There are no comments at the moment.