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 \leq N, M \leq 2 \times 10^{5}$

$1 \le X_i, X_j, Y_i, Y_j \le 10^9$ $1 \leq X_{i}, X_{j}, Y_{i}, Y_{j} \leq 10^{9}$

$Y_i \ne Y_k$ $Y_{i} \neq Y_{k}$ for all $1 \le i < k \le N$ $1 \leq i < k \leq N$

$X_j \ne X_k$ $X_{j} \neq X_{k}$ for all $1 \le j < k \le M$ $1 \leq j < k \leq M$

Subtask 1 [5%]

$1 \le X_i, Y_j, Y_i, Y_j \le 2\,000$ $1 \leq X_{i}, Y_{j}, Y_{i}, Y_{j} \leq 2 000$

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

Subtask 2 [10%]

$1 \le X_i, X_j, Y_i, Y_j \le 10^6$ $1 \leq X_{i}, X_{j}, Y_{i}, Y_{j} \leq 10^{6}$

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

Subtask 3 [15%]

$1 \le X_i, X_j, Y_i, Y_j \le 10^6$ $1 \leq X_{i}, X_{j}, Y_{i}, Y_{j} \leq 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

Copy

Sample Output

Copy

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.

8

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