GCC '16 P1 - Watching Anime

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


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
    sunnylancoder  commented on Dec. 21, 2016, 9:07 p.m.

    Can any of the A time periods overlap?

    • 1
      Kirito  commented on Dec. 21, 2016, 9:14 p.m. edited


      Ninja'd by r3mark feelz bad

    • 4
      r3mark  commented on Dec. 21, 2016, 9:14 p.m. edit 2

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

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

        He's just a really hard worker