Submission #1302671

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long


using Key = int;
using Val = int;

struct node_t{
  Key key;
  Val val;
  int pri;
  int cnt;
  int min;
  node_t *lch,*rch;
};

int count(node_t *t){return !t?0:t->cnt;}
int min(node_t *t){return !t?(1<<29):t->min;}

node_t* update(node_t *t){
  t->cnt = count(t->lch) + count(t->rch) + 1;
  t->min = min(t->val,min(min(t->lch),min(t->rch)));
  return t;
}
node_t *merge(node_t *l,node_t *r){
  if(!l||!r)return l ? l : r;

  if(l->pri > r->pri){  //左の部分木の方が優先度が高い場合
    l->rch = merge(l->rch,r);
    return update(l);
  }else{
    r->lch=merge(l,r->lch);
    return update(r);
  }
}

//k番目で分ける
pair<node_t*,node_t*>splitAt(node_t *t,int k){// [0,k),[k,n)
  if(!t)return make_pair(nullptr,nullptr);
  //
  if(k<=count(t->lch)){
    pair<node_t*,node_t*> s = splitAt(t->lch,k);
    t->lch=s.second;
    return make_pair(s.first,update(t));
  }else{
    pair<node_t*,node_t*> s = splitAt(t->rch,k-count(t->lch)-1);
    t->rch=s.first;
    return make_pair(update(t),s.second);
  }
}

//k(値)で分ける
pair<node_t*, node_t*> splitBy(node_t *t, Key k) { // [-inf, k), [k, inf)
	if (!t) return make_pair(nullptr, nullptr);

	if (k <= t->key) {
		auto s = splitBy(t->lch, k);
		t->lch = s.second;
		return make_pair(s.first, update(t));
	} else {
		auto s = splitBy(t->rch, k);
		t->rch = s.first;
		return make_pair(update(t), s.second);
	}
}

//vを代入
node_t* insert(node_t *t,Key key,int v){
  node_t* n = new node_t{ key,v,rand(),1,v};
  if(!t)return n;
  pair<node_t*,node_t*> x = splitBy(t,key);
  return merge(merge(x.first,n),x.second);
}

node_t* erase(node_t *t,int k){
  pair<node_t*,node_t*> x=splitAt(t,k);
  pair<node_t*,node_t*> y=splitAt(x.second,1);
  return merge(x.first,y.second);
}
node_t* kth(node_t *t, int k) {
	if (!t || count(t->lch) == k) return t;
	return count(t->lch) > k ? kth(t->lch, k)
		: kth(t->rch, k - count(t->lch) - 1);
}

signed main(){
  node_t* tree=nullptr;
  int q;cin>>q;
  for(int i=0;i<q;i++){
    int t,x;
    scanf("%lld %lld",&t,&x);
    if(t==1){
      tree=insert(tree,x,x);
    }else{
      x--;
      node_t* node = kth(tree,x);
      cout<<node->val<<endl;
      tree=erase(tree,x);
    }
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:93:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&t,&x);
                             ^

Judge Result