Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int Z = (int)1e5 + 111;
  6. const int INF = (int)1e9;
  7.  
  8. int l[Z], r[Z], b[Z], dp[Z];
  9.  
  10. int main() {
  11.   int m;
  12.   cin >> m;
  13.   l[Z - 1] = INF;
  14.   for (int i = 0; i <= m + 1; ++i)
  15.     b[i] = Z - 1;
  16.   for (int i = 1;; ++i) {
  17.     cin >> l[i] >> r[i];
  18.     if (l[i] == 0 && r[i] == 0)
  19.       break;
  20.     if (l[i] == r[i] || r[i] <= 0 || l[i] >= m) continue;
  21.     if (l[b[min(m, r[i])]] > l[i])
  22.       b[min(m, r[i])] = i;
  23.   }
  24.   for (int i = m; i; --i) {
  25.     if (l[b[i + 1]] < l[b[i]])
  26.       b[i] = b[i + 1];
  27.     if (i && i == l[b[i]] || b[i] == Z - 1) {
  28.       cout << "No solution";
  29.       exit(0);
  30.     }
  31.   }
  32.   vector<int> v;
  33.   for (int i = m; i;) {
  34.     v.push_back(b[i]);
  35.     i = max(0, l[b[i]]);
  36.   }
  37.   cout << v.size() << "\n";
  38.   vector<pair<int, int>> ans;
  39.   for (auto &x : v)
  40.     ans.push_back({l[x], r[x]});
  41.   sort(ans.begin(), ans.end());
  42.   for (auto &x : ans)
  43.     cout << x.first << " " << x.second << "\n";
  44.  
  45.   return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement