/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
上下左右に無限に広がる座標平面を考えます。
最初、座標平面全体は白色に塗られています。
この上で、次の形のクエリを Q 個行う事を考えます。
i 個目のクエリは次の形で与えられます。
(A_i,B_i) , (A_i,D_i) , (C_i,B_i) , (C_i,D_i) を頂点とする長方形領域を選び、その領域内の色を反転させる。すなわち、白色だった場所は黒色で塗り、黒色だった場所は白色で塗る。
すべてのクエリが終わった後、黒色で塗られている範囲の面積を求めてください。
制約
- 1 \leq Q \leq 10^5
- -10^9 \leq A_i < C_i \leq 10^9
- -10^9 \leq B_i < D_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 : A_Q B_Q C_Q D_Q
出力
すべてのクエリが終わった後、黒色で塗られている範囲の面積を出力せよ。
入力例 1
2 0 0 2 2 1 1 3 3
出力例 1
6
1 回目の操作の後では 2 \times 2 の正方形領域が黒く塗られています。
2 回目の操作の後で、 (1,1) , (1,2) , (2,1) , (2,2) で囲まれた正方形領域は白色に戻り、最終的に黒く塗られた領域の面積は 6 となります。
入力例 2
1 -1000000000 -1000000000 1000000000 1000000000
出力例 2
4000000000000000000
答えが 32 bit 整数に収まらない可能性があることに注意してください。
Score : 6 points
Warning
Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Consider an infinite coordinate plane.
Initially, the plane is entirely painted white.
Let us process the following Q queries on this plane.
The i-th query is in the following form:
Invert the rectangular region whose corners are (A_i,B_i), (A_i,D_i), (C_i,B_i), and (C_i,D_i). That is, the parts within the region that are painted white before this query will be painted black, and vice versa.
Find the area of the whole region painted black after all the queries.
Constraints
- 1 \leq Q \leq 10^5
- -10^9 \leq A_i < C_i \leq 10^9
- -10^9 \leq B_i < D_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 : A_Q B_Q C_Q D_Q
Output
Print the area of the whole region painted black after all the queries.
Sample Input 1
2 0 0 2 2 1 1 3 3
Sample Output 1
6
After the first query, a 2 \times 2 square region is painted black.
After the second query, a square region whose corners are (1,1), (1,2), (2,1), (2,2) is white again, so the final area of the whole region painted black is 6.
Sample Input 2
1 -1000000000 -1000000000 1000000000 1000000000
Sample Output 2
4000000000000000000
Note that the answer may not fit into a 32-bit integer type.