#1026626 (C++23) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	るこーそー
提出日時	2024-11-14 15:57:21
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	531 ms / 3,000 ms
コード長	7,030 bytes
コンパイル時間	3,316 ms
コンパイル使用メモリ	254,032 KB
実行使用メモリ	17,664 KB
最終ジャッジ日時	2024-11-14 15:57:33
合計ジャッジ時間	11,616 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	298 ms 6,820 KB
testcase_04	AC	214 ms 16,896 KB
testcase_05	AC	199 ms 17,664 KB
testcase_06	AC	221 ms 17,664 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	225 ms 8,448 KB
testcase_13	AC	228 ms 8,448 KB
testcase_14	AC	221 ms 8,576 KB
testcase_15	AC	233 ms 8,576 KB
testcase_16	AC	230 ms 9,088 KB
testcase_17	AC	256 ms 9,344 KB
testcase_18	AC	294 ms 9,856 KB
testcase_19	AC	318 ms 10,496 KB
testcase_20	AC	346 ms 10,880 KB
testcase_21	AC	382 ms 11,264 KB
testcase_22	AC	403 ms 12,032 KB
testcase_23	AC	436 ms 12,288 KB
testcase_24	AC	469 ms 12,928 KB
testcase_25	AC	497 ms 13,440 KB
testcase_26	AC	531 ms 13,824 KB
testcase_27	AC	3 ms 6,816 KB
testcase_28	AC	3 ms 6,816 KB
testcase_29	AC	3 ms 6,820 KB
testcase_30	AC	189 ms 8,448 KB
testcase_31	AC	199 ms 8,832 KB
testcase_32	AC	2 ms 6,820 KB
testcase_33	AC	2 ms 6,816 KB
testcase_34	AC	2 ms 6,816 KB
testcase_35	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

template<typename S, S (*op)(S,S), S (*e)(), typename F, S (*mapping)(F,S), F (*composition)(F,F), F (*id)()>
class SplayTree{
private:
    struct node{
        S v, prod;
        F lazy;
        int cnt, rev;
        node *l, *r;
        node(S v): v(v), prod(v), lazy(id()), cnt(1), rev(0){
            l = r = nullptr;
        }
    };

    node *root=nullptr;

    int count(node *x){return !x ? 0:x->cnt;}
    S sum(node *x){return !x ? e():x->prod;}

    void push(node *x){
        if (!x)return;
        if (x->lazy!=id()){
            x->v=mapping(x->lazy,x->v);
            x->prod=mapping(x->lazy,x->prod);
            if (x->l)x->l->lazy=composition(x->lazy,x->l->lazy);
            if (x->r)x->r->lazy=composition(x->lazy,x->r->lazy);
            x->lazy=id();
        }
        if (x->rev){
            swap(x->l,x->r);
            if (x->l)x->l->rev^=1;
            if (x->r)x->r->rev^=1;
            x->rev=0;
        }
    }

    void all_push(node *x){
        push(x);
        if (x)push(x->l),push(x->r);
    }

    node *update(node *x){
        if (!x)return x;
        x->cnt=count(x->l)+count(x->r)+1;
        x->prod=op(op(sum(x->l),x->v),sum(x->r));
        return x;
    }
    
    node *rotate(node *x,bool right){
        node *y= right ? x->l : x->r;
        all_push(x);all_push(y);
        if (!y)return x;
        if (right){
            x->l=y->r;
            y->r=x;
        }else{
            x->r=y->l;
            y->l=x;
        }
        update(x);update(y);
        return y;
    }

    node *splay(node *x,int k){
        if (!x)return nullptr;
        all_push(x);
        if (k<count(x->l)){
            if (x->l==nullptr)return x;
            if (k<count(x->l->l)){
                x->l->l=splay(x->l->l,k);
                x=rotate(x,true);
            }else if (count(x->l->l)<k){
                x->l->r=splay(x->l->r,k-count(x->l->l)-1);
                if (x->l->r)x->l=rotate(x->l,false);
            }
            return x->l ? rotate(x,true) : update(x);
        }else if (count(x->l)<k){
            if (x->r==nullptr)return x;
            k=k-count(x->l)-1;
            if (k<count(x->r->l)){
                x->r->l=splay(x->r->l,k);
                if (x->r->l)x->r=rotate(x->r,true);
            }else if (count(x->r->l)<k){
                x->r->r=splay(x->r->r,k-count(x->r->l)-1);
                x=rotate(x,false);
            }
            return x->r ? rotate(x,false) : update(x);
        }
        return update(x);
    }

    node *merge(node *l,node *r) {
        if (!l || !r) return !l ? r : l;
        r=splay(r,0);
        r->l=l;
        return update(r);
    }

    pair<node*, node*> split(node *x, int k) {
        assert(0<=k && k<=size());
        if (!x) return {nullptr, nullptr};
        if (k==size())return {x,nullptr};
        x=splay(x, k);
        node* l=x->l;
        x->l=nullptr;
        return {l,x};
    }

    tuple<node*, node*, node*> split3(node *x,int l,int r){//[0,l),[l,r),[r,size)
        auto [left_mid,right]=split(x,r);
        auto [left,mid]=split(left_mid,l);
        return {left,mid,right};
    }

    int bisect_left(node *x,S v){
        all_push(x);
        if (!x)return 0;
        if (v<=x->v)return bisect_left(x->l,v);
        return count(x->l)+1+bisect_left(x->r,v);
    }

    int bisect_right(node *x,S v){
        all_push(x);
        if (!x)return 0;
        if (v<x->v)return bisect_right(x->l,v);
        return count(x->l)+1+bisect_right(x->r,v);
    }

public:
    int size(){all_push(root);update(root);return (!root ? 0 : root->cnt);}
    
    void insert(int k,S v) {
        assert(0<=k && k<=size());
        auto [l,r]=split(root,k);
        root=merge(merge(l,new node(v)),r);
    }

    void erase(int k) {
        assert(0<=k && k<size());
        root=splay(root,k);
        auto [left_mid,right]=split(root,k+1);
        auto [left,mid]=split(left_mid,k);
        delete mid;
        root=merge(left,right);
    }

    SplayTree merge(SplayTree other){
        node *new_root=merge(root,other.root);
        SplayTree res;
        res.root=new_root;
        return res;
    }

    pair<SplayTree,SplayTree> split(int k){
        auto [left,right]=split(root,k);
        SplayTree l,r;
        all_push(left);all_push(right);
        update(left);update(right);
        l.root=left;r.root=right;
        return {l,r};
    }

    S get(int k){
        assert(0<=k && k<size());
        if (!root)return e();
        root=splay(root,k);
        all_push(root);
        update(root);
        return root->v;
    }

    void set(int k,S v){
        assert(0<=k && k<size());
        root=splay(root,k);
        root->v=v;
    }

    S prod(int l,int r) {
        assert(0<=l && r<=size() && l<=r);
        root=splay(root,l);
        auto [left,mid,right]=split3(root,l,r);
        all_push(mid);
        S res=sum(update(mid));
        root=merge(merge(left,mid),right);
        return res;
    }

    void apply(int l,int r,F f){
        assert(0<=l && r<=size() && l<=r);
        root=splay(root,l);
        auto [left,mid,right]=split3(root,l,r);
        if (mid)mid->lazy=composition(f,mid->lazy);
        root=merge(merge(left,mid),right);
    }

    void reverse(int l,int r){
        assert(0<=l && r<=size() && l<=r);
        root=splay(root,l);
        auto [left,mid,right]=split3(root,l,r);
        if (mid)mid->rev=1;
        root=merge(merge(left,mid),right);
    }

    void insert(int k,SplayTree other){
        assert(0<=k && k<=size());
        root=splay(root,k);
        all_push(root);
        auto [left,right]=split(root,k);
        root=merge(merge(left,other.root),right);
    }

    void erase(int l,int r){
        assert(0<=l && r<=size() && l<=r);
        root=splay(root,l);
        auto [left,mid,right]=split3(root,l,r);
        all_push(root);
        delete mid;
        root=merge(left,right);
    }
    int bisect_left(S v){root=splay(root,size());return bisect_left(root,v);}
    int bisect_right(S v){root=splay(root,size());return bisect_right(root,v);}
    void balance(){
        while (root && root->l && root->r && count(root->l)>2*count(root->r)){
            if (count(root->l)>count(root->r)){
                root=rotate(root,true);
            }else{
                root=rotate(root,false);
            }
        }
    }
};


using S=long long;
S op(S a,S b){return min(a,b);}
S e(){return 0;}
using F=long long;
S mapping(F f,S x){return f+x;}
F composition(F f,F g){return f+g;}
F id(){return 0;}

void solve() {
    SplayTree<S,op,e,F,mapping,composition,id> st;
    int q,k;
    cin >> q >> k;

    while (q--){
        long long t,x;
        cin >> t;
        if (t==1){
            cin >> x;
            st.insert(st.bisect_left(x),x);
        }else {
            if (k<=st.size()){
                cout << st.get(k-1) << endl;
                st.erase(k-1);
            }else{
                cout << -1 << endl;
            }
        }
        st.balance();
    }
}

int main() {
    solve();
}

yukicoder

結果

テストケース

ソースコード