Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define rep(i, a, b) for (int i = a; i <= b; ++i)
- #define per(i, b, a) for (int i = b; i >= a; --i)
- #define pb push_back
- #define sz(x) (int)(x).size()
- #define all(x) (x).begin(), (x).end()
- using namespace std;
- typedef long long ll;
- typedef vector< int > vi;
- typedef pair< int, int > pii;
- typedef long double ld;
- const int oo = 0x3f3f3f3f;
- const ll mod = 1000000007LL;
- int n;
- set < pii > st;
- int main() {
- cin >> n;
- rep (i, 1, n) {
- int a, b;
- cin >> a >> b;
- if (sz(st) == 0) {
- st.insert({a, b});
- continue;
- }
- pii el = *(--st.upper_bound({a, b}));
- st.erase(st.find(el));
- int c = el.first;
- int d = el.second;
- if (c <= b && d >= a) {
- st.insert({max(a, c), min(b, d)});
- } else {
- st.insert({a, b});
- st.insert({c, d});
- }
- }
- cout << sz(st) << '\n' ;
- for (auto x : st) cout << x.first << ' ';
- cout << '\n';
- // cerr << fixed() << setprecision(3) << (ld)clock() / (ld)CLOCKS_PER_SEC << '\n';
- return 0;
- }
Add Comment
Please, Sign In to add comment