DMOPC '17 Contest 4 P1 - Ribbon Colouring Fun

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

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

It is that time of the year when the carrot has to pay tribute to the magical rabbit overlord again! As a gift, the carrot decides to prepare an artfully coloured ribbon. She already has a purple ribbon of length N and width 1, but she wants it to be even more perfect, so she paints some parts of the ribbon blue. More specifically, she does Q paint strokes, with the ith stroke starting at x_i units from the left end and ending at y_i units from the left end, where x_i and y_i are both integers. Help her find the total area of purple and blue ribbon!


For all subtasks, 0 \le x_i < y_i \le N.

Subtask 1 [40%]

1 \le N,Q \le 1\,000

Subtask 2 [60%]

1 \le N,Q \le 100\,000

Input Specification

The first line of input will contain two integers, N and Q. The following Q lines will each contain two integers, x_i and y_i.

Output Specification

Two integers on the same line separated by a space, the first one representing the total purple area, and the second one the blue area.

Sample Input

4 3
0 2
1 2
3 4

Sample Output

1 3

Explanation for Sample Output

In the beginning, we have a purple ribbon of length 4. After the first update, the first half of the ribbon is blue. The second update completely overlaps with the first, so the ribbon does not change. The third update changes the last quarter to blue, so the total blue area is 3, and the purple area is 4-3=1.


  • 1
    31501357  commented on Dec. 9, 2019, 1:42 p.m.

    Why is this only worth five points?