Advertisement
ec1117

Untitled

Jan 29th, 2021
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 2e5;
  5.  
  6. vector<tuple<int, int, int>> seg;
  7. int a[MX], b[MX], ans[MX], n;
  8. pair<int, int> st[MX * 2];
  9.  
  10. void upd(int a, pair<int, int> val) {
  11.     a += n - 1;
  12.     st[a] = val;
  13.     for (a /= 2; a; a /= 2) {
  14.         st[a] = max(st[a * 2], st[a * 2 + 1]);
  15.     }
  16. }
  17.  
  18. pair<int, int> qry(int a, int b) {
  19.     pair<int, int> res;
  20.     for (a += n - 1, b += n - 1; a <= b; a /= 2, b /= 2) {
  21.         if (a % 2 == 1) {
  22.             res = max(res, st[a++]);
  23.         }
  24.         if (b % 2 == 0) {
  25.             res = max(res, st[b--]);
  26.         }
  27.     }
  28.     return res;
  29. }
  30.  
  31. int main() {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie(0);
  34.  
  35.     cin >> n;
  36.     for (int i = 0; i < n; ++i) {
  37.         cin >> a[i] >> b[i];
  38.         seg.emplace_back(a[i], b[i], i);
  39.     }
  40.     sort(seg.begin(), seg.end());
  41.  
  42.     int ndx = 0;
  43.     pair<int, int> swp;
  44.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> cur;
  45.     for (int i = 1; i <= n; ++i) {
  46.         while (ndx < n && get<0>(seg[ndx]) <= i) {
  47.             cur.emplace(get<1>(seg[ndx]), get<2>(seg[ndx]));
  48.             ++ndx;
  49.         }
  50.         int opt = cur.top().second;
  51.         ans[opt] = i;
  52.         cur.pop();
  53.         auto mat = qry(i, n);
  54.         if (mat.first >= a[opt]) {
  55.             swp = {mat.second, opt};
  56.         }
  57.         upd(b[opt], {i, opt});
  58.     }
  59.  
  60.     auto out = [&]() {
  61.         for (int i = 0; i < n; ++i) {
  62.             cout << ans[i] << ' ';
  63.         }
  64.         cout << '\n';
  65.     };
  66.  
  67.     if (swp.first || swp.second) {
  68.         cout << "NO" << '\n';
  69.         out();
  70.         swap(ans[swp.first], ans[swp.second]);
  71.         out();
  72.     } else {
  73.         cout << "YES" << '\n';
  74.         out();
  75.     }
  76. }
  77.  
  78.  
  79. const int MOD = 1000000007;
  80. const char nl = '\n';
  81. const int MX = 100001; //check the limits, dummy
  82.  
  83. int main() {
  84.     ios_base::sync_with_stdio(0); cin.tie(0);    
  85.    
  86.     int N; cin >> N;
  87.     vector<pair<int, pi> > A(N);
  88.     F0R(i, N) {
  89.         int X, Y; cin >> X >> Y;
  90.         X--; Y--;
  91.         A[i] = {X, {Y, i}};
  92.     }
  93.  
  94.     sort(all(A));
  95.  
  96.     priority_queue<pi, vpi, greater<pi> > q;
  97.     int nxt = 0;
  98.     int P1[N];
  99.     F0R(i, N) {
  100.         while (nxt < N && A[nxt].f == i) {
  101.             q.push(A[nxt].s);
  102.             nxt++;
  103.         }
  104.         pi cur = q.top(); q.pop();
  105.         P1[cur.s] = i;
  106.     }
  107.  
  108.     int P2[N]; F0R(i, N) P2[i] = P1[i];
  109.  
  110.     nxt = 0;
  111.     F0R(i, N) {
  112.         while (nxt < N && A[nxt].f == i) {
  113.             q.push(A[nxt].s);
  114.             nxt++;
  115.         }
  116.         pi cur = q.top(); q.pop();
  117.         if (sz(q)) {
  118.             pi ext = q.top();
  119.             if (cur.f >= P1[ext.s]) {
  120.                 P2[cur.s] = P1[ext.s];
  121.                 P2[ext.s] = i;
  122.                 goto good;
  123.             }
  124.         }
  125.     }
  126.     cout << "YES" << nl;
  127.     F0R(i, N) cout << P1[i]+1 << " ";
  128.     cout << nl;
  129.     return 0;
  130.  
  131.     good:
  132.     ;
  133.     cout << "NO" << nl;
  134.     F0R(i, N) cout << P1[i]+1 << " ";
  135.     cout << nl;
  136.     F0R(i, N) cout << P2[i]+1 << " ";
  137.     cout << nl;
  138.    
  139.     return 0;
  140. }
  141.  
  142. // read the question correctly (ll vs int)
  143. // template by bqi343
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement