結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
![]() |
提出日時 | 2018-02-09 22:42:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 322 ms / 3,000 ms |
コード長 | 3,125 bytes |
コンパイル時間 | 996 ms |
コンパイル使用メモリ | 73,624 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-10-08 16:36:28 |
合計ジャッジ時間 | 7,473 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In member function 'avl_tree<T>::node* avl_tree<T>::rank(node*, int) const [with T = std::pair<long long int, int>]': main.cpp:79:3: warning: control reaches end of non-void function [-Wreturn-type] 79 | } | ^
ソースコード
#include<algorithm> #include<iostream> #include<vector> // http://www.prefield.com/algorithm/container/avl_tree.html template <class T> struct avl_tree { 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_tree() { root = NULL; } pointer find(const 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) { root = erase(root, key); } node *erase(node *t, const T &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); } #define sz(t) (t ? t->size : 0) #define ht(t) (t ? t->height : 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) t->size = sz(t->child[0]) + sz(t->child[1]) + 1; if (s) 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) t->height = std::max(ht(t->child[0]), ht(t->child[1])) + 1; if (t) t->size = sz(t->child[0]) + sz(t->child[1]) + 1; return t; } pointer rank(int k) const { return rank(root, k); } pointer rank(node *t, int k) const { if (!t) 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); } }; using namespace std; typedef long long lint; typedef vector<int>vi; typedef pair<int,int>pii; #define rep(i,n)for(int i=0;i<(int)(n);++i) int main(){ int q,k; cin>>q>>k; avl_tree<pair<lint,int> > tr; int sz=0; rep(_,q){ int kind; cin>>kind; if(kind==1){ lint v; cin>>v; tr.insert(make_pair(v,_)); sz++; }else{ if(sz<k){ cout<<-1<<endl; continue; } avl_tree<pair<lint,int> >::pointer r=tr.rank(k-1); pair<lint,int> key=r->key; cout<<key.first<<endl; tr.erase(key); sz--; } } }