ICPC Vietnam National Programming Contest 2019


2019-11-02 17:00 AKDT

ICPC Vietnam National Programming Contest 2019


2019-11-02 22:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -560 days 17:55:19

Time elapsed


Time remaining


Problem K
Kingdom of Ants

The Chimera Ants are building their own kingdom!

There are $n$ ants numbered from $1$ to $n$. Each ant is responsible for kingdom construction in a rectangular region. More precisely, the $i$-th ant is assigned a rectangular region in Cartesian plane, with edges parallel to the two axes, and opposite corners at $(x_ i, y_ i)$ and $(u_ i, v_ i)$.

Some regions or parts of some regions might be assigned to multiple ants. Usually, this would pose no problem: when two ants disagree, all the ants assigned to this region will vote for the two options, and the option with more votes will be implemented. However, this method does not work if a non-zero, even number of ants are assigned to a region, as the voting result may be a tie. The ants would like to know what are the total area of such region. Please help them!


The first line of input contains a single integer $n$ $(1 \le n \le 10^5)$.

In the next $n$ line, the $i$-th line contains $4$ integers, $x_ i$, $y_ i$, $u_ i$ and $v_ i$ $(-10^9 \le x_ i, y_ i, u_ i, v_ i \le 10^9)$. $(x_ i, y_ i)$ and $(u_ i, v_ i)$ are the coordinates of the two opposite corners of the rectangular region assigned to the $i$-th ant.


Print a single integer — the total area assigned to a positive even number of ants.

Explanation of sample test

\includegraphics[width=0.45\textwidth ]{illustration.png}
Sample Input 1 Sample Output 1
10 10 20 20
15 15 25 30