P9737 [COCI 2022/2023 #2] Lampice

Teo’s balcony is a rectangular platform with length $n+1$ and width $m+1$. There are $2k$ colored lights on it. The color of each light is represented by a number from $1 \sim k$. For each color, there are exactly $2$ lights, and all their coordinates are positive integers. Teo considers a region on the balcony to be good if and only if: - This region is a rectangle, and all its sides are parallel to the sides of the balcony. - For the two lights of each color, either both are inside the region, or both are outside the region. - The coordinates of the top-left corner and the bottom-right corner of the region are both integers. - The length and width of the region are both **at least** $2$. Now Teo wants you to find how many good regions there are on his balcony. **Note: the bottom-left corner is $(0,0)$, and the top-right corner is $(n,m)$.**

The first line contains three integers $n$, $m$, $k$ ($1\le n\le150,1\le m\le1000,0\le k\le200000$), representing the length and width of the balcony, and the number of light colors. The next $k$ lines each contain four integers $x_1$, $y_1$, $x_2$, $y_2$. The $i$-th line gives the coordinates of the two lights of color $i$.

One line containing one integer, the number of good regions.

|$\text{Subtask}$|Score|Special Properties| |:-:|:-:|:-:| |$1$|$26$|For each color, $x_1=y_1=0$| |$2$|$12$|$n,m\le10$, $k\le1000$| |$3$|$35$|$m\le150$| |$4$|$37$|None| **The full score for this problem is $110$ points.** Translated by ChatGPT 5