DMPG '15 S5 - Black and White

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 2.0s
Java 8 4.0s
Memory limit: 256M
Java 8 256M
Author:

Problem type

Ruby is playing with the board from a board game.

The board consists of N\times N square cells of unit dimensions on a plane, with the topmost left tile defined as (0,0). Originally, all of these cells are colored black. Ruby will execute M commands of the form x, y, w, h, in which she'll flip the colors of the cells contained by a w\times h rectangle whose top-left vertex is located at (x, y). That is, a cell colored black will become white, and a cell colored white will become black.

At the end of all her flip commands, she wants to know the area covered by white tiles on the board.

Constraints

Subtask 1 [10%]
  • 10 \le N \le 1\,000
  • 1 \le M \le 100
Subtask 2 [30%]
  • N = 1\,000
  • 1\,000 \le M \le 100\,000
Subtask 3 [60%]
  • N = 10\,000
  • 1\,000 \le M \le 100\,000

Input Specification

The first line of input will contain 2 space-separated integers N and M. The next M lines will each contain a flip command in the form of 4 space-separated integers x, y, w, h (0 \le x, y; 1 \le x + w, y + h \le N).

Output Specification

On one line, the integer number of cells that are colored white at the end of Ruby's game.

Sample Input 1

10 2
0 0 10 10
2 2 6 6

Sample Output 1

64

Explanation

The board after the 2 commands is shown below.

Sample Input 2

10 15
0 5 10 5
0 0 1 1
6 5 2 1
3 6 1 1
3 5 1 1
7 2 2 1
4 2 1 1
3 3 1 2
0 8 1 2
6 9 2 1
8 2 1 1
1 2 2 1
1 3 2 2
3 3 2 2
6 2 1 1

Sample Output 2

54

Explanation

The board after all 15 commands is shown below.


Comments


  • 2
    septence123  commented on May 14, 2017, 12:19 p.m.

    Why is pypy or python's time limit not 4 seconds, but java's is?


    • -1
      root  commented on June 11, 2017, 3:55 p.m.

      Python didn't exist when this problem was authored.


      • 2
        max  commented on Dec. 1, 2017, 1:41 a.m. edited

        The programming language Python was conceived in the late 1980s, and its implementation was started in December 1989 by Guido van Rossum...

        Source: Wikipedia

        This problem was written in 2015.


        • -6
          Beautiful_Times  commented on Dec. 5, 2017, 12:05 p.m.

          Wikipedia isn't a trusted source


          • -2
            ZippIE  commented on Dec. 5, 2017, 8:54 p.m.

            His point is that Python was invented before this question was written.


  • 0
    root  commented on May 13, 2017, 9:24 p.m.

    For the second example, there is only one command with y=0 that flips a single square in the first row, but the first row on the board is quite complex, how is this possible?


    • 2
      wleung_bvg  commented on May 14, 2017, 1:17 a.m.

      y is the column number, not the row number


  • -7
    1yangdan  commented on May 13, 2017, 2:33 p.m. edited

    Da di da Use short for dp


  • 9
    bobhob314  commented on Oct. 28, 2015, 2:59 p.m.
    HBD

    Happy birthday T-man.


    • 5
      Xyene  commented on Oct. 29, 2015, 1:35 p.m.

      Thanks!