Submission #1383330

---

Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

unsigned xorShift() {
	static unsigned z = time(NULL);
	z ^= z << 13; z ^= z >> 17; z ^= z << 5;
	return z;
}

struct node {
  int val;
  node *ch[2];
  int pri;
  int cnt; //部分木のサイズ
  int sum; //部分木の値の和

  node(int v, double p): val(v),pri(p),cnt(1),sum(v) {
    ch[0] = ch[1] = nullptr;
  }
};

int count(node *t) {return t == nullptr ? 0: t->cnt;}
int sum(node *t) {return t == nullptr ? 0: t->sum;}

node *update(node *t) {
  t->cnt = count(t->ch[0]) + count(t->ch[1]) + 1;
  t->sum = sum(t->ch[0]) + sum(t->ch[1]) + t->val;
  return t;
}

// b=0で左回転、b=1で右回転
node *rotate(node *t, int b) {
  node *s = t->ch[1-b];
  t->ch[1-b] = s->ch[b];
  s->ch[b] = t;
  update(t);
  update(s);
  return s;
}

node *insert(node *t, int val, int pri) {
  if(t == nullptr) return new node(val, pri);
  else if(val == t->val) return t;
  else if(val < t->val) {
    t->ch[0] = insert(t->ch[0], val, pri);
    if(t->pri > t->ch[0]->pri) {
      t = rotate(t, 1);
    }
  } else{
    t->ch[1] = insert(t->ch[1], val, pri);
    if(t->pri > t->ch[1]->pri) {
      t = rotate(t, 0);
    }
  }
  return update(t);
}

node *erase(node *t, int x) {
  if (t->val == x) {
    if (t->ch[0] && t->ch[1]) {
      if (t->ch[0]->pri < t->ch[1]->pri) {
        t = rotate(t, 1);
        t->ch[1] = erase(t->ch[1], x);
        return update(t);
      } else {
        t = rotate(t, 0);
        t->ch[0] = erase(t->ch[0], x);
        return update(t);
      }
    } else {
      return t->ch[0] ? t->ch[0] : t->ch[1];
    }
  } else if (x < t->val) {
    t->ch[0] = erase(t->ch[0], x);
  } else {
    t->ch[1] = erase(t->ch[1], x);
  }
  return update(t);
}

int level(node *t, int k) {
  if(k < count(t->ch[0])) return level(t->ch[0], k);
  if(k == count(t->ch[0])) return t->val;
  return level(t->ch[1], k-count(t->ch[0])-1);
}

void print(node *t) {
  if(t == nullptr) return;
  print(t->ch[0]);
  cout << (t->val) << " ";
  print(t->ch[1]);
}

signed main(void)
{
  int q;
  cin >> q;

  node *root = nullptr;
  REP(i, q) {
    int t, x;
    cin >> t >> x;
    double p = xorShift();
    if(t == 1) {
      root = insert(root, x, p);
    } else {
      int k = level(root, x-1);
      root = erase(root, k);
      cout << k << endl;
    }
    //print(root);
    //cout << endl;
  }

  return 0;
}

Submission Info

Judge Result