結果
問題 | No.649 ここでちょっとQK! |
ユーザー | untan007 |
提出日時 | 2020-08-11 11:10:15 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 265 ms
5,248 KB |
testcase_04 | AC | 91 ms
15,872 KB |
testcase_05 | AC | 92 ms
15,744 KB |
testcase_06 | AC | 47 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 74 ms
9,088 KB |
testcase_13 | AC | 76 ms
8,960 KB |
testcase_14 | AC | 78 ms
8,960 KB |
testcase_15 | AC | 79 ms
8,832 KB |
testcase_16 | AC | 77 ms
9,088 KB |
testcase_17 | AC | 85 ms
9,728 KB |
testcase_18 | AC | 94 ms
10,112 KB |
testcase_19 | AC | 108 ms
10,624 KB |
testcase_20 | AC | 118 ms
11,264 KB |
testcase_21 | AC | 131 ms
11,776 KB |
testcase_22 | AC | 137 ms
12,416 KB |
testcase_23 | AC | 148 ms
12,928 KB |
testcase_24 | AC | 159 ms
13,312 KB |
testcase_25 | AC | 169 ms
14,208 KB |
testcase_26 | AC | 173 ms
14,720 KB |
testcase_27 | AC | 3 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 60 ms
7,424 KB |
testcase_31 | AC | 63 ms
7,168 KB |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | AC | 1 ms
5,248 KB |
testcase_35 | AC | 1 ms
5,248 KB |
ソースコード
#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; }