English · Original
Chinese · Translation
Formal · Original
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.
## Input
The first line contains a single integer $n$ ($1 \le n \le 100\,000$) — the number of rectangles.
The $i$\-th of the next $n$ lines contains $4$ integers $x_1$, $y_1$, $x_2$ and $y_2$ ($-10^9 \le x_1 < x_2 \le 10^9$, $-10^9 \le y_1 < y_2 \le 10^9$) — the coordinates of corners of the $i$\-th rectangle.
## Output
In the single line print the number of different colors in the plane, including color $0$.
[samples]
## Note
<center> 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.
</center>
[{"iden":"statement","content":"Arkady 有一张涂满颜色 $0$ 的无限平面。然后他依次画出 $n$ 个边与笛卡尔坐标轴平行的矩形，每个矩形用油漆填充。第 $i$ 个矩形的颜色为 $i$（矩形按绘制顺序从 $1$ 到 $n$ 编号）。新矩形可能完全或部分覆盖之前的矩形。\n\n在 Arkady 画完所有矩形后，计算平面上不同颜色的数量。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100 thin 000$) —— 矩形的数量。\n\n接下来的 $n$ 行中，第 $i$ 行包含 $4$ 个整数 $x_1$, $y_1$, $x_2$ 和 $y_2$ ($-10^9 lt.eq x_1 < x_2 lt.eq 10^9$, $-10^9 lt.eq y_1 < y_2 lt.eq 10^9$) —— 第 $i$ 个矩形的两个对角顶点坐标。\n\n在一行中输出平面上不同颜色的数量，包括颜色 $0$。\n\n这就是第二个样例中平面的样子\n\n$0$ = 白色，$1$ = 青色，$2$ = 蓝色，$3$ = 紫色，$4$ = 黄色，$5$ = 红色。 "},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100 thin 000$) —— 矩形的数量。第 $i$ 行包含 $4$ 个整数 $x_1$, $y_1$, $x_2$ 和 $y_2$ ($-10^9 lt.eq x_1 < x_2 lt.eq 10^9$, $-10^9 lt.eq y_1 < y_2 lt.eq 10^9$) —— 第 $i$ 个矩形的两个对角顶点坐标。"},{"iden":"output","content":"在一行中输出平面上不同颜色的数量，包括颜色 $0$。"},{"iden":"examples","content":"输入\n5\n-1 -1 1 1\n-4 0 0 4\n0 0 4 4\n-4 -4 0 0\n0 -4 4 0\n输出\n5\n\n输入\n4\n0 0 4 4\n-4 -4 0 0\n0 -4 4 0\n-2 -4 2 4\n输出\n5"},{"iden":"note","content":"这就是第一个样例中平面的样子\n\n这就是第二个样例中平面的样子\n\n$0$ = 白色，$1$ = 青色，$2$ = 蓝色，$3$ = 紫色，$4$ = 黄色，$5$ = 红色。 "}]}
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of rectangles.
For each $ i \in \{1, \dots, n\} $, let $ R_i = [x_{i,1}, x_{i,2}) \times [y_{i,1}, y_{i,2}) $ denote the axis-aligned rectangle drawn at step $ i $, with color $ i $.
Let $ R_0 = \mathbb{R}^2 \setminus \bigcup_{i=1}^n R_i $ denote the initial background region with color $ 0 $.
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. For each $ i \in \{1, \dots, n\} $:
$ -10^9 \leq x_{i,1} < x_{i,2} \leq 10^9 $,
$ -10^9 \leq y_{i,1} < y_{i,2} \leq 10^9 $
**Objective**
Compute the number of distinct colors present on the plane after all rectangles are drawn, where the color of a point is determined by the *last* rectangle (highest index $ i $) that covers it, or $ 0 $ if uncovered by any rectangle.
Formally, define the final color function $ c: \mathbb{R}^2 \to \{0, 1, \dots, n\} $ as:
$$
c(p) =
\begin{cases}
0 & \text{if } p \notin \bigcup_{i=1}^n R_i \\
\max\{ i \in \{1, \dots, n\} \mid p \in R_i \} & \text{otherwise}
\end{cases}
$$
Let $ C = \{ c(p) \mid p \in \mathbb{R}^2 \} $.
Output $ |C| $.
API Response (JSON)
{
"problem": {
"name": "D. Arkady and Rectangles",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF983D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Arkady 有一张涂满颜色 $0$ 的无限平面。然后他依次画出 $n$ 个边与笛卡尔坐标轴平行的矩形，每个矩形用油漆填充。第 $i$ 个矩形的颜色为 $i$（矩形按绘制顺序从 $1$ 到 $n$ 编号）。新矩形可能完全或部分覆盖之前的矩形。\\n\\n在 Arkady 画完所有矩形后，计算平面上不同颜色的数量。\\n\\n第一行包含一个整数...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of rectangles. \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ R_i = [x_{i,1}, x_{i,2}) \\times [y_{i,1}, y_{i,2}) $ denote the axis-aligned recta...",
"is_translate": false,
"language": "Formal"
}
]
}