After her previous
artwork was met with critical acclaim, Bessie was offered a job designing
painting sets. She designs these paintings by choosing \(1\le N\le 10^5\)
axis-aligned rectangles in the plane such that no two edges are collinear. The
boundaries of these rectangles define the boundaries of the painting's colored
regions.

Still being an avant-garde artist, Bessie decides that the painting should
resemble a Holstein cow. More specifically, each region formed by the rectangles
is colored either black or white, no two adjacent regions have the same color,
and the region outside of all the rectangles is colored white.

After choosing the rectangles, Bessie would like you to output one of two things
based on a parameter \(T\):

• If \(T=1\), output the total number of regions.
• If \(T=2\), output the number of white regions followed by the number of black regions.

*Note: the time limit for this problem is 4s, twice the default.*

Problem credits: Andi Qu

SCORING

1. Test cases 3-4 satisfy \(N\le 10^3\).
2. In test cases 5-7, no two rectangle boundaries intersect.
3. In test cases 8-10, \(T=1\) and the boundaries of all rectangles are connected.
4. In test cases 11-13, \(T=2\) and the boundaries of all rectangles are connected.
5. In test cases 14-18, \(T=1\).
6. In test cases 19-23, \(T=2\).

Problem credits: Andi Qu

The first line contains \(N\) and \(T\).

The next \(N\) lines each contain the description of a rectangle in the form
\((x_1,y_1), (x_2,y_2)\) where \(1\le x_1 and \(1\le y_1.
\((x_1, y_1)\) and \((x_2, y_2)\) are the bottom left and top right corners of the
rectangle respectively.

It is guaranteed that all the \(x_i\) form a permutation of \(1\ldots 2N\), and the
same holds for all the \(y_i\).

A single integer if \(T=1\), otherwise two separated by spaces.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > February > Platinum