Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <vector>
- using namespace std;
- vector < int > answer;
- int f(int x, vector < int > v)
- {
- int max = -INT_MIN, max_i;
- if (x < int(v.size()) - 1)
- {
- for (int i = x + 1; i < int(v.size()); i++)
- if (v[i] > max)
- max = v[i] + 1;
- }
- else
- max = 0;
- return max;
- }
- void w(int x, vector <int > v, vector < int > c)
- {
- int max = -1, max_i;
- for (int i = x + 1; i < int(v.size()); i++)
- if (c[i] >= max)
- {
- max = c[i];
- max_i = i;
- }
- answer.push_back(max_i);
- if (c[max_i] > 0)
- w(v[max_i], v, c);
- }
- int main()
- {
- int n, x, y;
- vector < pair < int, int > > a;
- vector < pair < int, int > > coordinate;
- vector < int > b;
- cin >> n;
- for (int i = 0; i < n; i++)
- {
- cin >> x >> y;
- a.push_back(make_pair(x, y));
- }
- sort(a.begin(), a.end());
- for (int i = 0; i < n; i++)
- {
- coordinate.push_back(make_pair(a[i].first, i));
- coordinate.push_back(make_pair(a[i].second, i));
- }
- sort(coordinate.begin(), coordinate.end());
- int open = 0;
- for (int i = 0; i < n * 2; i++)
- {
- if (int(b.size()) <= coordinate[i].second)
- {
- b.push_back(-1);
- open = coordinate[i].second;
- }
- else
- b[coordinate[i].second] = open;
- }
- vector < int > c = b;
- for (int i = int(b.size()) - 1; i >= 0; i--)
- c[i] = f(b[i], c);
- c[0] += 1;
- int max = -1, max_i;
- for (int i = 0; i < n; i++)
- if (c[i] > max)
- {
- max = c[i];
- max_i = i;
- }
- answer.push_back(max_i);
- w(b[max_i], b, c);
- cout << answer.size() << endl;
- for (int i = 0; i < int(answer.size()); i++)
- cout << a[answer[i]].first << ' '<< a[answer[i]].second << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment