## DMPG '15 S5 - Black and White

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Java 1.8s
Memory limit: 256M

Author:
Problem type

Ruby is playing with the board from a board game.

The board consists of square cells of unit dimensions on a plane, with the topmost left tile defined as . Originally, all of these cells are colored black. Ruby will execute commands of the form , , , , in which she'll flip the colors of the cells contained by a rectangle whose top-left vertex is located at . 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.

#### Input Specification

The first line of input will contain 2 space-separated integers and .

The next lines will each contain a flip command in the form of 4 space-separated integers , , , .

#### 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.

• commented on May 5, 2022, 7:53 p.m.

Since the original data were weak, a new test case was added to subtask and .

• commented on July 8, 2019, 10:12 p.m.

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

• commented on July 9, 2019, 1:03 p.m.

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

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

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

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

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

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

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

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

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

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

• 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?

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

y is the column number, not the row number

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

Happy birthday T-man.

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

Thanks!