DMOPC '20 Contest 4 P3 - Roving Roombas

View as PDF

Submit solution


Points: 12 (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


  • 24
    JohnstonLiu  commented on March 15, 2021, 5:36 a.m.

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


    • 1
      Riolku  commented on Feb. 11, 2022, 5:18 p.m.

      Uh... it is, lol.


  • 3
    EpicChadGamer  commented on March 15, 2021, 4:29 a.m. edit 2

    #define int long long


    • 9
      31501357  commented on April 16, 2021, 4:01 a.m.

      That's so cringe.


      • 7
        thomas_li  commented on April 16, 2021, 6:19 p.m.

        no u


    • 8
      c_zqz  commented on March 15, 2021, 6:03 a.m. edit 3

      inspire my grad quote