GCC '16 P1 - Watching Anime

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M
Authors:
Kirito, r3mark
Problem type

A certain weeb wants to watch anime. However, he has C commitments over the next 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 periods of time. Given his schedule over the next N hours, figure out the total amount of time he can watch anime for.

Input Specification

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

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

Output Specification

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

Sample Input 1

20 3 2
1 3
2 4
3 10
1 4
10 20

Sample Output 1

5

Explanation for Sample Output 1

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

Sample Input 2

20 3 2
1 20
3 5
6 8
1 10
1 20

Sample Output 2

0

Comments


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

    Can any of the A time periods overlap?


    • 1
      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.


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

        He's just a really hard worker