CF983D.Arkady and Rectangles

NOI/NOI+/CTSC

通过率:0%

时间限制:4.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Arkady has got an infinite plane painted in color 00. Then he draws nn rectangles filled with paint with sides parallel to the Cartesian coordinate axes, one after another. The color of the ii-th rectangle is ii (rectangles are enumerated from 11 to nn 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.

阿尔卡季得到了一个被涂成颜色 00 的无限平面。然后,他依次画出 nn 个边与笛卡尔坐标轴平行的实心矩形,每个矩形使用一种新颜色进行填充。第 ii 个矩形的颜色为 ii(矩形按绘制顺序从 11 编号至 nn)。新绘制的矩形可能完全或部分覆盖之前已绘制的矩形。

请计算阿尔卡季画完所有矩形后,平面上不同颜色的总数。

输入格式

The first line contains a single integer nn (1≤n≤100 0001 \le n \le 100\,000) — the number of rectangles.

The ii-th of the next nn lines contains 44 integers x1x_1, y1y_1, x2x_2 and y2y_2 (−109≤x1<x2≤109-10^9 \le x_1 \lt x_2 \le 10^9, −109≤y1<y2≤109-10^9 \le y_1 \lt y_2 \le 10^9) — the coordinates of corners of the ii-th rectangle.

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

接下来的 nn 行中,第 ii 行包含 44 个整数 x1x_1、y1y_1、x2x_2 和 y2y_2(−109≤x1<x2≤109-10^9 \le x_1 \lt x_2 \le 10^9,−109≤y1<y2≤109-10^9 \le y_1 \lt y_2 \le 10^9)—— 第 ii 个矩形的两个对角顶点的坐标。

输出格式

In the single line print the number of different colors in the plane, including color 00.

在单行中输出平面上不同颜色的数量(包括颜色 00)。

输入输出样例

  • 输入#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

00 = white, 11 = cyan, 22 = blue, 33 = purple, 44 = yellow, 55 = red.

这是第一个样例中平面的外观。

这是第二个样例中平面的外观。

00 = 白色,11 = 青色,22 = 蓝色,33 = 紫色,44 = 黄色,55 = 红色。

输入解题思路,AI测评打分。不知道怎么写?

首页