Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int Z = (int)1e5 + 111;
- const int INF = (int)1e9;
- int l[Z], r[Z], b[Z], dp[Z];
- int main() {
- int m;
- cin >> m;
- l[Z - 1] = INF;
- for (int i = 0; i <= m + 1; ++i)
- b[i] = Z - 1;
- for (int i = 1;; ++i) {
- cin >> l[i] >> r[i];
- if (l[i] == 0 && r[i] == 0)
- break;
- if (l[i] == r[i] || r[i] <= 0 || l[i] >= m) continue;
- if (l[b[min(m, r[i])]] > l[i])
- b[min(m, r[i])] = i;
- }
- for (int i = m; i; --i) {
- if (l[b[i + 1]] < l[b[i]])
- b[i] = b[i + 1];
- if (i && i == l[b[i]] || b[i] == Z - 1) {
- cout << "No solution";
- exit(0);
- }
- }
- vector<int> v;
- for (int i = m; i;) {
- v.push_back(b[i]);
- i = max(0, l[b[i]]);
- }
- cout << v.size() << "\n";
- vector<pair<int, int>> ans;
- for (auto &x : v)
- ans.push_back({l[x], r[x]});
- sort(ans.begin(), ans.end());
- for (auto &x : ans)
- cout << x.first << " " << x.second << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement