結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2018-02-09 23:13:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 348 ms / 3,000 ms |
コード長 | 3,170 bytes |
コンパイル時間 | 1,586 ms |
コンパイル使用メモリ | 162,664 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-10-08 22:20:42 |
合計ジャッジ時間 | 8,140 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In member function ‘AVL<T>::node* AVL<T>::rank(AVL<T>::node*, long long int) [with T = long long int]’: main.cpp:95:3: warning: control reaches end of non-void function [-Wreturn-type] 95 | } | ^
ソースコード
#include<bits/stdc++.h>#define int long longusing namespace std;using Int = long long;//BEGIN CUT HEREtemplate<typename T>struct AVL{struct node{T key;int size,height;node *child[2];node (const T &key):key(key),size(1),height(1){child[0]=child[1]=0;}} *root;typedef node *pointer;AVL(){root=NULL;}pointer find(T key){return find(root,key);}node *find(node *t,const T key){if(t==NULL) return NULL;if(key==(t->key)) return t;else if(key<(t->key)) return find(t->child[0],key);else return find(t->child[1],key);}void insert(const T key){root=insert(root,new node(key));}node *insert(node *t,node *x){if(t==NULL) return x;if((x->key)<=(t->key)) t->child[0]=insert(t->child[0],x);else t->child[1]=insert(t->child[1],x);t->size+=1;return balance(t);}void erase(const T key){T t=key;if(find(t)==NULL) return;root=erase(root,key);}node *erase(node *t,const int x){if(t==NULL) return NULL;if(x==(t->key)){return move_down(t->child[0],t->child[1]);}else{if(x<(t->key)) t->child[0]=erase(t->child[0],x);else t->child[1]=erase(t->child[1],x);t->size-=1;return balance(t);}}node *move_down(node *t,node *rhs){if(t==NULL) return rhs;t->child[1]=move_down(t->child[1],rhs);return balance(t);}int sz(node *t){if(t!=NULL) return t->size;return 0;}int ht(node *t){if(t!=NULL) return t->height;return 0;}node *rotate(node *t,int l,int r){node *s=t->child[r];t->child[r]=s->child[l];s->child[l]=balance(t);if(t!=NULL) t->size=sz(t->child[0])+sz(t->child[1])+1;if(s!=NULL) s->size=sz(s->child[0])+sz(s->child[1])+1;return balance(s);}node *balance(node *t){for(int i=0;i<2;i++){if(ht(t->child[!i])-ht(t->child[i])<-1){if(ht(t->child[i]->child[!i])-ht(t->child[i]->child[i])>0)t->child[i]=rotate(t->child[i],i,!i);return rotate(t,!i,i);}}if(t!=NULL) t->height=max(ht(t->child[0]),ht(t->child[1]))+1;if(t!=NULL) t->size=sz(t->child[0])+sz(t->child[1])+1;return t;}pointer rank(int k){return rank(root,k);}pointer rank(node *t,int k){if(t==NULL) return NULL;int m=sz(t->child[0]);if(k<m) return rank(t->child[0],k);if(k==m) return t;if(k>m) return rank(t->child[1],k-m-1);}int index(T key){if(find(key)==NULL) return -1;return index(root,key);}int index(node *t,T key){if(key==(t->key)) return sz(t->child[0]);if(key<(t->key)) return index(t->child[0],key);else return sz(t)-sz(t->child[1])+index(t->child[1],key);}};signed main(){Int q, k;cin >> q >> k;AVL<Int> avl;Int sz = 0;for(int i=0;i<q;i++){Int t, x;cin >> t;if(t==1){cin >> x;avl.insert(x);sz++;}else{if(sz < k){cout << -1 << endl;continue;}Int key=avl.rank(k-1)->key;cout<<key<<endl;avl.erase(key);sz--;}}return 0;}