SHARE
TWEET

Untitled

a guest Apr 21st, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Solution By Chynti :)
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 3e5+10;
  7.  
  8. typedef struct Treap* treap;
  9.  
  10. struct Treap {
  11.     int x, y, cnt;
  12.     treap l, r;
  13.     Treap(int _x) {
  14.         cnt = 1, x = _x, y = rand();
  15.         l = r = NULL;
  16.     }
  17. };
  18.  
  19. int cnt(treap t) {
  20.     return t ? t->cnt : 0;
  21. }
  22.  
  23. void upd_cnt(treap t) {
  24.     if (t)
  25.         t->cnt = cnt(t->l) + cnt(t->r) + 1;
  26. }
  27.  
  28.  
  29. void spl(treap t, treap &l, treap &r, int x, int add = 1) {
  30.     if (!t)
  31.         return void(l = r = NULL);
  32.     int cur_x = add + cnt(t->l);
  33.     if (cur_x < x)
  34.         spl(t->r, t->r, r, x, cur_x + 1), l = t;
  35.     else
  36.         spl(t->l, l, t->l, x, add), r = t;
  37.     upd_cnt(l);
  38.     upd_cnt(r);
  39.     upd_cnt(t);
  40. }
  41.  
  42.  
  43. void mer(treap &t, treap l, treap r) {
  44.     if (!l || !r)
  45.         t = l ? l : r;
  46.     else if (l->y > r->y)
  47.         mer(l->r, l->r, r), t = l;
  48.     else
  49.         mer(r->l, l, r->l), t = r;
  50.     upd_cnt(t);
  51. }
  52.  
  53. treap t;
  54.  
  55. int n, m;
  56. int p[N], a[N];
  57. vector <int> res;
  58.  
  59. int find_set(int a) {
  60.     if (p[a] == a)
  61.         return a;
  62.     return p[a] = find_set(p[a]);
  63. }
  64.  
  65. void prin(treap t) {
  66.     if (!t) return;
  67.     prin(t->l);
  68.     res.push_back(t->x);
  69.     if (t->x) n--;
  70.     if (!n) {
  71.         cout << res.size() << endl;
  72.         for (int i = 0; i < res.size(); i++)
  73.             cout << res[i] << " ";
  74.         exit(0);
  75.     }
  76.     prin(t->r);
  77. }
  78.  
  79. int main() {
  80.     scanf("%d%d", &n, &m);
  81.     for (int i = 1; i <= 300000; i++) {
  82.         p[i] = i;
  83.         mer(t, t, new Treap(0));
  84.     }
  85.  
  86.     for (int i = 1, x; i <= n; i++) {
  87.         scanf("%d", &x);
  88.         treap a, b, c, d;
  89.         spl(t, a, b, x);
  90.         spl(b, b, c, find_set(x)+1 - cnt(a));
  91.         spl(b, b, d, find_set(x) - cnt(a));
  92.         mer(b, b, c);
  93.         mer(b, new Treap(i), b);
  94.         mer(t, a, b);
  95.         p[find_set(x)] = find_set(x) + 1;
  96.     }
  97.     prin(t);
  98. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top