← 返回题目列表

Codeforces · 1389/F

F. 双色段

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

您将获得 $$$n$$$ 段 $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$。每个段都有两种颜色之一:第 $$$i$$$ 段的颜色是 $$$t_i$$$。

如果满足以下两个条件,我们称一对线段 $$$i$$$ 和 $$$j$$$ 为坏线段:

- $$$t_i \ne t_j$$$;
- 线段 $$$[l_i, r_i]$$$ 和 $$$[l_j, r_j]$$$ 相交、嵌入或接触,i。 e.存在一个整数$$$x$$$,使得$$$x \in [l_i, r_i]$$$ 和$$$x \in [l_j, r_j]$$$。

计算可以从给定的段中选择的最大数量,以便所选段中不存在坏对。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 段数。

接下来的 $$$n$$$ 行包含三个整数 $$$l_i, r_i, t_i$$$ ($$$1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\}$$$) - 第 $$$i$$$ 段的描述。

输出

打印可以选择的最大段数,以便所选段之间不存在坏对。

示例

输入 #1

3
1 3 1
4 6 2
2 5 1

输出 #1

2

输入 #2

5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2

输出 #2

4

输入 #3

7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1

输出 #3

5