← 返回题目
题库练习 「USACO 2022.2 Platinum」Paint by Rectangles
← 上一题 下一题 →

A6127 | 「USACO 2022.2 Platinum」Paint by Rectangles

时间限制4s
内存限制512MB
通过 / 提交0/0

题目描述

**题目译自 [USACO 2022 February Contest, Platinum](http://usaco.org/index.php?page=feb22results) Problem 1. [Paint by Rectangles](http://usaco.org/index.php?page=viewproblem2&cpid=1212)**

在平面上画 $N$（$1\le N\le 10^5$）个矩形，这些矩形将平面分割成若干个区域，可以将这些区域进行黑白染色，规定其中面积无穷大的区域为白色。

给定参数 $T$，若 $T=1$，输出总共的区域数，否则先输出白色区域的数量，再输出黑色区域的数量。

输入格式

第一行输入两个正整数 $N$ 和 $T$。

接下来 $N$ 行输入矩形的两角 $(x_1,y_1)$ 和 $(x_2, y_2)$，保证 $1\le x_1<x_2\le 2N$，$1\le y_1<y_2\le 2N$，且所有的 $x_i$、所有的 $y_i$ 各自构成 $1,\dots,2N$ 的排列。

输出格式

如果 $T=1$ 输出一个整数，否则输出两个整数。

输入输出样例

输入 #1
2 1
1 1 3 3
2 2 4 4
输出 #1
4
输入 #2
5 2
1 5 3 6
5 4 7 9
4 1 8 3
9 8 10 10
2 2 6 7
输出 #2
4 5
C++ 编辑器
输入
输出