結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー るこーそー
提出日時 2024-11-13 21:36:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,428 ms / 3,000 ms
コード長 5,775 bytes
コンパイル時間 3,636 ms
コンパイル使用メモリ 254,004 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2024-11-13 21:36:24
合計ジャッジ時間 22,884 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In instantiation of 'S SplayTree<S, op, e, F, mapping, composition, id>::get(int) [with S = long long int; S (* op)(S, S) = op; S (* e)() = e; F = long long int; S (* mapping)(F, S) = mapping; F (* composition)(F, F) = composition; F (* id)() = id]':
main.cpp:202:23:   required from here
main.cpp:145:26: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
  145 |         if (!root)return NULL;
      |                          ^~~~

ソースコード

diff # 

#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};
    }

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){
        return SplayTree(merge(root, other.root));
    }

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

    S get(int k){
        assert(0<=k && k<size());
        if (!root)return NULL;
        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);
    }
};

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;

    auto lb=[&](S x){
        int ng=-1,ok=st.size();
        while (ok-ng>1){
            int mid=(ok+ng)/2;
            if (st.get(mid)<x)ng=mid;
            else ok=mid;
        }
        return ok;
    };

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

int main() {
    solve();
}
0