307650: CF1389F. Bicolored Segments
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Bicolored Segments
题意翻译
### 题目描述 给你 $n$ 条线段 $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$。线段有两种颜色,第 $i$ 条线段的颜色为 $t_i$。 我们称一对线段 $i, j$ 是不好的,当且仅当以下两个条件同时满足: - $t_i \neq t_j$; - 线段 $[l_i, r_i]$ 和 $[l_j, r_j]$ 相交、相嵌或相切。换句话说,存在这样一个整数 $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$ 条线段。 ### 输出格式 输出一行一个整数,表示最多可以选择给定的这些线段中的多少条,使得选择的线段中没有任何一对线段是不好的。题目描述
You are given $ n $ segments $ [l_1, r_1], [l_2, r_2], \dots, [l_n, r_n] $ . Each segment has one of two colors: the $ i $ -th segment's color is $ t_i $ . Let's call a pair of segments $ i $ and $ j $ bad if the following two conditions are met: - $ t_i \ne t_j $ ; - the segments $ [l_i, r_i] $ and $ [l_j, r_j] $ intersect, embed or touch, i. e. there exists an integer $ x $ such that $ x \in [l_i, r_i] $ and $ x \in [l_j, r_j] $ . Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — number of segments. The next $ n $ lines contains three integers $ l_i, r_i, t_i $ ( $ 1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\} $ ) — description of the $ i $ -th segment.
输出格式
Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.
输入输出样例
输入样例 #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