GCC '16 P1 - Watching Anime - Olympiads Online Judge

GCC '16 P1 - Watching Anime

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

Problem type

A certain weeb wants to watch anime. However, he has $C$ $C$ commitments over the next $N$ $N$ hours, during which he cannot watch anime. To make matters worse, he is using a low quality streaming site that is only available for $A$ $A$ periods of time. Given his schedule over the next $N$ $N$ hours, figure out the total amount of time he can watch anime for.

Input Specification

The first line will contain 3 integers $N$ $N$ $(1 \le N \le 10^9)$ $(1 \leq N \leq 10^{9})$ , $A$ $A$ $(1 \le A \le 10^5)$ $(1 \leq A \leq 10^{5})$ , $C$ $C$ $(1 \le C \le 10^5)$ $(1 \leq C \leq 10^{5})$ .
The next $A$ $A$ lines consist of 2 integers, $a_i, b_i$ $a_{i}, b_{i}$ $(1 \le a_i \le b_i \le N)$ $(1 \leq a_{i} \leq b_{i} \leq N)$ , indicating that anime is streaming from hour $a_i$ $a_{i}$ to $b_i$ $b_{i}$ , inclusive.
The next $C$ $C$ lines consist of 2 integers, $c_i, d_i$ $c_{i}, d_{i}$ $(1 \le c_i \le d_i \le N)$ $(1 \leq c_{i} \leq d_{i} \leq N)$ , indicating that the weeb in question cannot watch anime from hour $c_i$ $c_{i}$ to $d_i$ $d_{i}$ , inclusive.

For $10\%$ $10 %$ of points, $N \le 1\,000$ $N \leq 1 000$ .

Output Specification

The total amount of anime this weeb can watch, in hours.

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

The weeb can watch anime from hour 5 to hour 9.

Sample Input 2

Copy

Sample Output 2

Copy

Comments

0

sunnylancoder commented on Dec. 22, 2016, 2:07 a.m.

Can any of the A time periods overlap?

2

Kirito commented on Dec. 22, 2016, 2:14 a.m. ← edited →

Yes.

Ninja'd by r3mark feelz bad

5

r3mark commented on Dec. 22, 2016, 2:14 a.m. ← edit 2 →

Yes. C time periods may overlap as well. In retrospect, it makes no sense to have overlapping commitments.

13

onlyIfStatement commented on Dec. 22, 2016, 5:42 a.m.

He's just a really hard worker