DMPG '15 S5 - Black and White

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 1.0s
Java 1.8s
Memory limit: 256M
Author:
Xyene
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 \le N-1; 1 \le w, h \le N; 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 for Sample Output 1

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 for Sample Output 2

The board after all 15 commands is shown below.

Comments


  • 0
    AryanG  commented on July 9, 2019, 2:12 a.m.

    I'm hitting TLE for the last subtask. Is there a better algorithm than just iterating somewhat cleverly?


    • 2
      4fecta  commented on July 9, 2019, 5:03 p.m. ← edited

      Your updates are still too slow. To pass the last subtask, try to reach \mathcal{O}(1) update time for each query.


  • 7
    septence123  commented on May 14, 2017, 4:19 p.m. ← edited

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


    • -17
      root  commented on June 11, 2017, 7:55 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • 15
        max  commented on Dec. 1, 2017, 6: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.


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

          This comment is hidden due to too much negative feedback. Show it anyway.


          • 5
            ZippIE  commented on Dec. 6, 2017, 1:54 a.m.

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


  • 1
    root  commented on May 14, 2017, 1:24 a.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?


    • 3
      wleung_bvg  commented on May 14, 2017, 5:17 a.m.

      y is the column number, not the row number


  • 15
    bobhob314  commented on Oct. 28, 2015, 6:59 p.m.

    Happy birthday T-man.


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

      Thanks!