Repository navigation
Expand file tree
/
Copy pathA.cpp
More file actions
61 lines (59 loc) · 1.43 KB
/
Copy pathA.cpp
File metadata and controls
61 lines (59 loc) · 1.43 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
void MergeSort(std::vector<std::pair<int, int> >& a) {
int n = a.size();
if (n <= 1) {
return;
}
std::vector<std::pair<int, int> > left(a.begin(), a.begin() + n / 2);
std::vector<std::pair<int, int> > right(a.begin() + n / 2, a.end());
MergeSort(left);
MergeSort(right);
a.clear();
size_t l = 0;
size_t r = 0;
while (l < left.size() && r < right.size()) {
if (left[l].first < right[r].first) {
a.push_back(left[l]);
++l;
} else {
a.push_back(right[r]);
++r;
}
}
while (l < left.size()) {
a.push_back(left[l]);
++l;
}
while (r < right.size()) {
a.push_back(right[r]);
++r;
}
}
int main() {
int n;
std::cin >> n;
std::vector<std::pair<int, int> > a(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i].first >> a[i].second;
}
MergeSort(a);
std::vector<std::pair<int, int> > ans;
int max_right = a[0].second;
int cur_first = 0;
for (int i = 1; i < n; ++i) {
if (max_right >= a[i].first) {
max_right = std::max(a[i].second, max_right);
} else {
ans.push_back(std::make_pair(a[cur_first].first, max_right));
cur_first = i;
max_right = a[i].second;
}
}
ans.push_back(std::make_pair(a[cur_first].first, max_right));
std::cout << ans.size() << "\n";
for (int i = 0; i < (int)ans.size(); ++i) {
std::cout << ans[i].first << ' ' << ans[i].second << "\n";
}
return 0;
}