DMOPC '20 Contest 4 P3 - Roving Roombas - Olympiads Online Judge

DMOPC '20 Contest 4 P3 - Roving Roombas

Points: 12 (partial)

Time limit: 2.0s

Memory limit: 256M

Authors:

Problem type

Tudor is managing his Roombas!

Tudor has a total of $N$ ~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)$ ~(0, Y_i)~ to $(X_i, Y_i)$ ~(X_i, Y_i)~.

Unfortunately, Tudor also has $M$ ~M~ server cords, each taking up parts of a column in his room, specifically, going from $(X_j, 0)$ ~(X_j, 0)~ to $(X_j, Y_j)$ ~(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 N, M \le 2 \times 10^5~

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

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

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

Subtask 1 [5%]

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

$1 \le N, M \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 X_i, X_j, Y_i, Y_j \le 10^6~

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

Subtask 3 [15%]

$1 \le X_i, X_j, Y_i, Y_j \le 10^6$ ~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$ ~2~ integers $N$ ~N~ and $M$ ~M~.

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

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

Output Specification

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

Sample Input

Sample Output

Explanation

$\text{[math]}$

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

Comments

26

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.

6

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.

9

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

no u

9

c_zqz commented on March 15, 2021, 6:03 a.m. ← edit 3 →

inspire my grad quote