← 返回题目列表

Codeforces · 983/D

D. 阿尔卡季和矩形

中文机器翻译题面 查看原题

Arkady 有一个无限的平面,颜色为$$$0$$$。然后他画了 $$$n$$$ 个充满颜料的矩形,这些矩形的边与笛卡尔坐标轴平行,一个接一个。第 $$$i$$$ 矩形的颜色是 $$$i$$$ (矩形按照他绘制的顺序从 $$$1$$$ 到 $$$n$$$ 枚举)。新的矩形可能完全或部分覆盖以前的一些矩形。

计算Arkady绘制完所有矩形后平面上不同颜色的数量。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — 矩形的数量。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$4$$$ 整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$ 和 $$$y_2$$$ ($$$-10^9 \le x_1 < x_2 \le 10^9$$$, $$$-10^9 \le y_1 < y_2 \le 10^9$$$) — 第 $$$i$$$ 个矩形的角点坐标。

输出

在单行中打印平面中不同颜色的数量,包括颜色 $$$0$$$。

示例

输入 #1

5
-1 -1 1 1
-4 0 0 4
0 0 4 4
-4 -4 0 0
0 -4 4 0

输出 #1

5

输入 #2

4
0 0 4 4
-4 -4 0 0
0 -4 4 0
-2 -4 2 4

输出 #2

5

注意

这就是飞机在第一个样本中的外观 这就是飞机在第二个样本中的外观 $$$0$$$ = 白色,$$$1$$$ = 青色,$$$2$$$ = 蓝色,$$$3$$$ = 紫色,$$$4$$$ = 黄色,$$$5$$$ = 红色。