DMOPC '20 Contest 4 P3 - Roving Roombas

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

Tudor is managing his Roombas!

Tudor has a total of N Roombas which he uses to clean his room. His Roombas each clean parts of a row in his square room, specifically, going from (0, Y_i) to (X_i, Y_i).

Unfortunately, Tudor also has M server cords, each taking up parts of a column in his room, specifically, going from (X_j, 0) to (X_j, Y_j).

Tudor is going to let his Roombas clean his room, and he wonders: how many times will any Roomba run over a cord? Note that if a Roomba runs over the end of a cord, it still counts.

Constraints

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

1 \le X_i, X_j, Y_i, Y_j \le 10^9

Y_i \ne Y_k for all 1 \le i < k \le N

X_j \ne X_k for all 1 \le j < k \le M

Subtask 1 [5%]

1 \le X_i, Y_j, Y_i, Y_j \le 2\,000

1 \le N, M \le 2\,000

Subtask 2 [10%]

1 \le X_i, X_j, Y_i, Y_j \le 10^6

1 \le N, M \le 2\,000

Subtask 3 [15%]

1 \le X_i, X_j, Y_i, Y_j \le 10^6

Subtask 4 [70%]

No additional constraints.

Input Specification

The first line contains 2 integers N and M.

The next N lines each contain 2 space-separated integers X_i and Y_i, representing the path of a Roomba.

The next M lines each contain 2 space-separated integers X_j and Y_j, representing a cord.

Output Specification

On one line, output the number of times any Roomba will run over a cord.

Sample Input

3 3
7 2
7 5
5 7
3 1
7 5
4 5

Sample Output

4

Explanation

The Roombas are shown going left to right, and the cords from the bottom up. There are four points of intersection.


Comments


  • -3
    andy_zhu23  commented on March 19, 2021, 2:59 p.m.

    2 5 5 3 8 5 4 9 2 7 5 9 3 2 1 7

    Answer is 8


  • 17
    JohnstonLiu  commented on March 15, 2021, 1:36 a.m.

    Notice how roombas move horizontally like rows and cords are vertical like columns. Coincidence? I think not!


  • 1
    EpicChadGamer  commented on March 15, 2021, 12:29 a.m. edit 2

    #define int long long


    • 7
      31501357  commented on April 16, 2021, 12:01 a.m.

      That's so cringe.


    • 5
      c_zqz  commented on March 15, 2021, 2:03 a.m. edit 3

      inspire my grad quote