CF1389F-Bicolored Segments
题目:
题目描述:
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:
1
2
3
4
| 3
1 3 1
4 6 2
2 5 1
|
样例输出 1:
样例输入 2:
1
2
3
4
5
6
| 5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2
|
样例输出 2:
样例输入 3:
1
2
3
4
5
6
7
8
| 7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1
|
样例输出 3:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include "ybwhead/ios.h"
int n;
const int maxn = 3e5 + 10;
int l[maxn], r[maxn], t[maxn];
vector<pair<int, pair<int, int>>> a;
set<pair<int, int>> s[2];
int main()
{
yin >> n;
for (int i = 1; i <= n; i++)
{
yin >> l[i] >> r[i] >> t[i];
--t[i];
a.push_back(make_pair(l[i], make_pair(0, i)));
a.push_back(make_pair(r[i], make_pair(1, i)));
}
sort(a.begin(), a.end());
int ans = 0;
for (auto x : a)
{
int i = x.second.second;
if (x.second.first)
{
int j = t[i];
int k = j ^ 1;
// cout << s[j].size() << " " << k << endl;
if (s[j].erase(make_pair(r[i], i)) && !s[k].empty())
{
// cout << i << endl;
++ans;
s[k].erase(s[k].begin());
}
}
else
{
s[t[i]].insert(make_pair(r[i], i));
}
// puts("!!!");
}
yout << n - ans << endl;
return 0;
}
|