結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー untan007
提出日時 2020-08-11 11:10:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 265 ms / 3,000 ms
コード長 10,345 bytes
コンパイル時間 1,098 ms
コンパイル使用メモリ 96,504 KB
実行使用メモリ 15,872 KB
最終ジャッジ日時 2024-10-09 11:17:04
合計ジャッジ時間 5,526 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <string>
#include <numeric>
#include <queue>
#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pl pair<ll,ll>
#define inf 1001001001001001000
//#define mod 1000000007
#define mod 998244353
#define pi 3.1415926535
using namespace std;
struct __INIT {
	__INIT() {
		cin.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(15);
	}
}__init;

struct node {
	node* left = NULL;
	node* right = NULL;
	node* parent = NULL;
	ll height = 0;
	ll size = 1;
	ll dup = 1;
	//first:value second:count
	ll value;
	ll getLheight() { return (left == NULL) ? 0 : left->height; }
	ll getRheight() { return (right == NULL) ? 0 : right->height; }
	void setHeight() {
		if (left == NULL && right == NULL) height = 0;
		else height = max(getLheight(), getRheight()) + 1;
	}
	ll getLsize() { return (left == NULL) ? 0 : left->size; }
	ll getRsize() { return (right == NULL) ? 0 : right->size; }
	void setSize() { size = getLsize() + getRsize() + dup; }
};

//template<typename T>
struct AvlTree {
public:
	node *root;
	AvlTree() { root = NULL; }
	AvlTree(ll r) {
		root = new node();
		root->value = r;
	}
	void insert(ll x) {
		node* now = root;
		if (now == NULL) {
			root = new node();
			root->value = x;
			return;
		}
		while (1) {
			if (x < now->value) {
				if (now->left != NULL) now = now->left;
				else {
					now->left = new node();
					now->left->value = x;
					now->left->parent = now;
					break;
				}
			}
			else if (x > now->value) {
				if (now->right != NULL) now = now->right;
				else {
					now->right = new node();
					now->right->value = x;
					now->right->parent = now;
					break;
				}
			}
			else {
				now->dup++;
				break;
			}
		}
		balance(now);
	}

	//最後の一つを消すことは想定してない
	//無い値は消せない
	void del(ll x) {
		node* n = root;
		while (n->value != x) {
			if (x < n->value) n = n->left;
			else n = n->right;
		}
		if (n->dup > 1) {
			n->dup--;
			while(n != NULL){
			    n->setSize();
			    n = n->parent;
			}
			return;
		}
		if (n->left != NULL) {
			node* kwr = n->left;
			while (kwr->right != NULL) kwr = kwr->right;
			n->value = kwr->value;
			n->dup = kwr->dup;
			if (n->left->value == kwr->value) {
				n->left = kwr->left;
				if (kwr->left != NULL) {
					kwr->left->parent = n;
				}
				kwr->parent = NULL;
				kwr->left = NULL;
				balance(n);
			}
			else {
				kwr->parent->right = kwr->left;
				if (kwr->left != NULL) {
					kwr->left->parent = kwr->parent;
				}
				balance(kwr->parent);
				kwr->parent = NULL;
				kwr->left = NULL;
			}
		}
		else if (n->right != NULL) {
			node* kwr = n->right;
			while (kwr->left != NULL) kwr = kwr->left;
			n->value = kwr->value;
			n->dup = kwr->dup;
			if (kwr->value == n->right->value) {
				n->right = kwr->right;
				if (kwr->right != NULL) {
					kwr->right->parent = n;
				}
				kwr->parent = NULL;
				kwr->right = NULL;
				balance(n);
			}
			else {
				kwr->parent->left = kwr->right;
				if (kwr->right != NULL) {
					kwr->right->parent = kwr->parent;
				}
				balance(kwr->parent);
				kwr->parent = NULL;
				kwr->right = NULL;
			}
		}
		else {
		    if(n->parent == NULL){
		        root = NULL;
		        return;
		    }
			if (n->parent->left != NULL && n->parent->left->value == n->value) {
				n->parent->left = NULL;
			}
			else {
				n->parent->right = NULL;
			}
			balance(n->parent);
		}
	}
	
	void delAll(ll x){
	    node* n = root;
		while (n->value != x) {
			if (x < n->value) n = n->left;
			else n = n->right;
		}
		if (n->dup > 1) {
			n->dup = 1;
			node* p = n;
			while(p != NULL){
			    p->setSize();
			    p = p->parent;
			}
		}

		if (n->left != NULL) {
			node* kwr = n->left;
			while (kwr->right != NULL) kwr = kwr->right;
			n->value = kwr->value;
			n->dup = kwr->dup;
			if (n->left->value == kwr->value) {
				n->left = kwr->left;
				if (kwr->left != NULL) {
					kwr->left->parent = n;
				}
				kwr->parent = NULL;
				kwr->left = NULL;
				balance(n);
			}
			else {
				kwr->parent->right = kwr->left;
				if (kwr->left != NULL) {
					kwr->left->parent = kwr->parent;
				}
				balance(kwr->parent);
				kwr->parent = NULL;
				kwr->left = NULL;
			}
		}
		else if (n->right != NULL) {
			node* kwr = n->right;
			while (kwr->left != NULL) kwr = kwr->left;
			n->value = kwr->value;
			n->dup = kwr->dup;
			if (kwr->value == n->right->value) {
				n->right = kwr->right;
				if (kwr->right != NULL) {
					kwr->right->parent = n;
				}
				kwr->parent = NULL;
				kwr->right = NULL;
				balance(n);
			}
			else {
				kwr->parent->left = kwr->right;
				if (kwr->right != NULL) {
					kwr->right->parent = kwr->parent;
				}
				balance(kwr->parent);
				kwr->parent = NULL;
				kwr->right = NULL;
			}
		}
		else {
		    if(n->parent == NULL){
		        root = NULL;
		        return;
		    }
			if (n->parent->left != NULL && n->parent->left->value == n->value) {
				n->parent->left = NULL;
			}
			else {
				n->parent->right = NULL;
			}
			balance(n->parent);
		}
	}

	void balance(node* n) {
		while (n != NULL) {
			n->setHeight();
			n->setSize();
			// rrotate chance
			if (n->getLheight() - 2 == n->getRheight()) {
				if (n->left->getLheight() - 1 == n->left->getRheight() || n->left->getLheight() == n->left->getRheight()) {
					rrotate(n);
				}
				else {
					lrotate(n->left);
					rrotate(n);
				}
			}
			if (n->getRheight() - 2 == n->getLheight()) {
				//cout<<"balance "<<n->value<<endl;
				if (n->right->getRheight() - 1 == n->right->getLheight() || n->right->getRheight() == n->right->getLheight()) {
					lrotate(n);
				}
				else {
					rrotate(n->right);
					lrotate(n);
				}
			}
			n = n->parent;
		}
	}

	void rrotate(node* n) {
		node* lnode = n->left;
		auto v = n->value;
		ll d = n->dup;
		n->value = lnode->value;
		n->dup = lnode->dup;
		lnode->value = v;
		lnode->dup = d;
		n->left = lnode->left;
		if (lnode->left != NULL) {
			(lnode->left)->parent = n;
		}
		lnode->left = lnode->right;
		lnode->right = n->right;
		if (n->right != NULL) {
			(n->right)->parent = lnode;
		}
		n->right = lnode;
		lnode->setHeight();
		lnode->setSize();
		n->setHeight();
		n->setSize();
	}

	void lrotate(node* n) {
		node* rnode = n->right;
		auto v = n->value;
		ll d = n->dup;
		n->value = rnode->value;
		n->dup = rnode->dup;
		rnode->value = v;
		rnode->dup = d;
		n->right = rnode->right;
		if (rnode->right != NULL) {
			rnode->right->parent = n;
		}
		rnode->right = rnode->left;
		rnode->left = n->left;
		if (n->left != NULL) {
			n->left->parent = rnode;
		}
		n->left = rnode;
		rnode->setHeight();
		rnode->setSize();
		n->setHeight();
		n->setSize();
	}

	ll findMax() {
		node *n = root;
		if (n == NULL) return -inf;
		while (n->right != NULL) n = n->right;
		return n->value;
	}

	ll findMin() {
		node *n = root;
		if (n == NULL) return inf;
		while (n->left != NULL) n = n->left;
		return n->value;
	}
	//k番目に小さい値
	ll findKMin(ll k,node* n) {
	    if(n == NULL) return inf;
		if (k > n->size) return inf;
		if (k <= n->getLsize()) return findKMin(k, n->left);
		else if (k > n->size - n->getRsize()) return findKMin(k-(n->size-n->getRsize()), n->right);
		else return n->value;
	}
	
	ll getSize(){
	    if(root != NULL) return root->size;
	    else return 0;
	}

	void show(node *n) {
	    if(n == NULL) return;
		cout << n->value << " lh:" << n->getLheight() << " rh:" << n->getRheight() <<" ls:"<<n->getLsize() <<" rs:" << n->getRsize() <<" size:"<<n->size <<" dup:"<<n->dup<< endl;
		if (n->left == NULL && n->right == NULL) {
			cout << "leafe" << endl;
		}
		else {
			if (n->left != NULL) show(n->left);
			if (n->right != NULL) show(n->right);
		}
	}
};

template<typename T>
struct SegmentTree{
    ll n;
    T ident;
    vector<T> node;
public:
    SegmentTree(vector<AvlTree> &v,T ide){
        ll sz = v.size();
        n = 1;
        ident = ide;
        while(n<sz) n*=2;
        node.resize(2*n-1,ident);
        
        //一番下に元配列を代入
        rep(i,sz){
            if(v[i].findMax() != -inf) node[i+n-1] = v[i].findMax();
            else node[i+n-1] = inf;
        }
        
        //子供の小さいほうをとってく
        //ここは問題によって変わる
        mrep(i,n-2) node[i] = product(node[2*i+1],node[2*i+2]);
    }
    
    SegmentTree(ll nn,T ide){
        ll sz = nn;
        n = 1;
        ident = ide;
        while(n<sz) n*=2;
        node.resize(2*n-1,ident);
        
        //一番下に元配列を代入
        //rep(i,sz) node[i+n-1] = inf;
        
        //子供の小さいほうをとってく
        //ここは問題によって変わる
        mrep(i,n-2) node[i] = product(node[2*i+1],node[2*i+2]);
    }
    
    SegmentTree(){}
    
    void update(ll x,T val){
        //一番下にアクセス
        x += (n-1);
        
        node[x] = val;
        while(x>0){
            x = (x-1)/2;
            node[x] = product(node[2*x+1],node[2*x+2]);
        }
    }
    //区間[a,b)を探す
    T get(ll a,ll b,ll k=0,ll l=0,ll r=-1){
        //最初は区間[0,n)
        if(r<0) r=n;
        
        //返しても常に問題ない値を返してね(minならinf、相和なら0)
        if(r <= a || b <= l) return ident;
        
        if(a<=l && r<=b) return node[k];
        
        ll lv = get(a,b,2*k+1,l,(l+r)/2);
        ll rv = get(a,b,2*k+2,(l+r)/2,r);
        return product(lv,rv);
    }
    
    T product(T &a,T &b){
        if(a == -inf) a = ident;
        if(b == -inf) b = ident;
        return min(a,b);
    }
};



int main(void) {
    ll q,k;
    cin>>q>>k;
    AvlTree at;
    rep(i, q){
        ll t;
        cin>>t;
        if(t == 1){
            ll v;
            cin>>v;
            at.insert(v);
        }
        else{
            ll ans = at.findKMin(k,at.root);
            if(ans == inf) cout<<-1<<endl;
            else{
                cout<<ans<<endl;
                at.del(ans);
            }
        }
    }
	return 0;
}
0