RKS_The_Great

Untitled

Mar 18th, 2018
359
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define rep(i, a, b) for (int i = a; i <= b; ++i)
  4. #define per(i, b, a) for (int i = b; i >= a; --i)
  5.  
  6. #define pb push_back
  7. #define sz(x) (int)(x).size()
  8. #define all(x) (x).begin(), (x).end()
  9.  
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef vector< int > vi;
  14. typedef pair< int, int > pii;
  15. typedef long double ld;
  16.  
  17. const int oo = 0x3f3f3f3f;
  18. const ll mod = 1000000007LL;
  19.  
  20. int n;
  21. set < pii > st;
  22.  
  23. int main() {
  24.     cin >> n;
  25.     rep (i, 1, n) {
  26.         int a, b;
  27.         cin >> a >> b;
  28.         if (sz(st) == 0) {
  29.             st.insert({a, b});
  30.             continue;
  31.         }
  32.         pii el = *(--st.upper_bound({a, b}));
  33.         st.erase(st.find(el));
  34.         int c = el.first;
  35.         int d = el.second;
  36.         if (c <= b && d >= a) {
  37.             st.insert({max(a, c), min(b, d)});
  38.         } else {
  39.             st.insert({a, b});
  40.             st.insert({c, d});
  41.         }
  42.     }
  43.  
  44.     cout << sz(st) << '\n'   ;
  45.     for (auto x : st) cout << x.first << ' ';
  46.     cout << '\n';
  47.  
  48. //  cerr << fixed() << setprecision(3) << (ld)clock() / (ld)CLOCKS_PER_SEC << '\n';
  49.     return 0;
  50. }
Add Comment
Please, Sign In to add comment