CF1608E The Cells on the Paper

在一张无限大的方格纸上，选中了 $n$ 个格子并用三种颜色进行染色，其中 $n$ 能被 $3$ 整除。已知每种颜色恰好有 $\frac{n}{3}$ 个被标记的格子。 请你求出最大的 $k$，使得可以从每种颜色中各选出 $\frac{k}{3}$ 个格子，移除其他所有被标记的格子，然后选择三个边平行于网格线的矩形，使得满足以下条件： - 任意两个矩形不能相交（但可以有公共边界），也就是说，任意两个矩形的交集面积必须为 $0$。 - 第 $i$ 个矩形恰好包含所有被选中的第 $i$ 种颜色的格子，且不包含其他颜色被选中的格子，对于 $i=1,2,3$。

输入的第一行包含一个整数 $n$，表示被标记的格子数（$3 \leq n \le 10^5$，$n$ 能被 $3$ 整除）。 接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i$、$y_i$、$c_i$（$|x_i|,|y_i| \leq 10^9$；$1 \leq c_i \leq 3$），其中 $(x_i, y_i)$ 表示第 $i$ 个被标记格子的坐标，$c_i$ 表示其颜色。 保证所有输入的格子 $(x_i, y_i)$ 均不相同，且每种颜色恰好有 $\frac{n}{3}$ 个格子。

输出一个整数 $k$，表示你最多能保留的格子数。

在第一个样例中，可以保留编号为 $1, 5, 6, 7, 8, 9$ 的 $6$ 个格子。 在第二个样例中，可以保留编号为 $1, 2, 3$ 的 $3$ 个格子。 由 ChatGPT 4.1 翻译