CF983D.Arkady and Rectangles
NOI/NOI+/CTSC
通过率:0%
时间限制:4.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Arkady has got an infinite plane painted in color 0. Then he draws n rectangles filled with paint with sides parallel to the Cartesian coordinate axes, one after another. The color of the i-th rectangle is i (rectangles are enumerated from 1 to n in the order he draws them). It is possible that new rectangles cover some of the previous ones completely or partially.
Count the number of different colors on the plane after Arkady draws all the rectangles.
阿尔卡季得到了一个被涂成颜色 0 的无限平面。然后,他依次画出 n 个边与笛卡尔坐标轴平行的实心矩形,每个矩形使用一种新颜色进行填充。第 i 个矩形的颜色为 i(矩形按绘制顺序从 1 编号至 n)。新绘制的矩形可能完全或部分覆盖之前已绘制的矩形。
请计算阿尔卡季画完所有矩形后,平面上不同颜色的总数。
输入格式
The first line contains a single integer n (1≤n≤100000) — the number of rectangles.
The i-th of the next n lines contains 4 integers x1, y1, x2 and y2 (−109≤x1<x2≤109, −109≤y1<y2≤109) — the coordinates of corners of the i-th rectangle.
第一行包含一个整数 n(1≤n≤100000)—— 矩形的数量。
接下来的 n 行中,第 i 行包含 4 个整数 x1、y1、x2 和 y2(−109≤x1<x2≤109,−109≤y1<y2≤109)—— 第 i 个矩形的两个对角顶点的坐标。
输出格式
In the single line print the number of different colors in the plane, including color 0.
在单行中输出平面上不同颜色的数量(包括颜色 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
说明/提示
That's how the plane looks in the first sample
That's how the plane looks in the second sample
0 = white, 1 = cyan, 2 = blue, 3 = purple, 4 = yellow, 5 = red.
这是第一个样例中平面的外观。
这是第二个样例中平面的外观。
0 = 白色,1 = 青色,2 = 蓝色,3 = 紫色,4 = 黄色,5 = 红色。
输入解题思路,AI测评打分。不知道怎么写?