結果

問題 No.151 セグメントフィッシング
ユーザー latte0119latte0119
提出日時 2015-10-26 21:18:26
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,468 bytes
コンパイル時間 2,269 ms
コンパイル使用メモリ 164,108 KB
実行使用メモリ 8,104 KB
最終ジャッジ日時 2023-10-11 12:53:20
合計ジャッジ時間 5,573 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 64 ms
8,056 KB
testcase_18 AC 91 ms
8,032 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In constructor ‘RBST::node::node(long long int)’:
main.cpp:8:36: warning: ‘*<unknown>.RBST::node::sum’ is used uninitialized in this function [-Wuninitialized]
         node(int val):val(val),sum(sum),cnt(1),lch(NULL),rch(NULL){}
                                    ^~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct RBST{
    struct node{
        node *lch,*rch;
        int val,sum,cnt;
        node(int val):val(val),sum(sum),cnt(1),lch(NULL),rch(NULL){}
    };

    node *root;
    RBST():root(NULL){}

    inline int count(node *t){return t?t->cnt:0;}
    inline int sum(node *t){return t?t->sum:0;}

    node *update(node *t){
        if(!t)return t;
        t->cnt=count(t->lch)+count(t->rch)+1;
        t->sum=sum(t->lch)+sum(t->rch)+t->val;
        return t;
    }

    node *merge(node *a,node *b){
        if(!a)return b;
        if(!b)return a;
        if(rand()%(count(a)+count(b))<count(a)){
            a->rch=merge(a->rch,b);
            return update(a);
        }
        else{
            b->lch=merge(a,b->lch);
            return update(b);
        }
    }

    pair<node *,node *>split(node *t,int k){
        if(!t)return make_pair(t,t);
        if(k<=count(t->lch)){
            pair<node *,node *>s=split(t->lch,k);
            t->lch=s.second;
            return make_pair(s.first,update(t));
        }
        else{
            pair<node *,node *>s=split(t->rch,k-count(t->lch)-1);
            t->rch=s.first;
            return make_pair(update(t),s.second);
        }
    }
    void insert(int k,int x){
        pair<node *,node *>s=split(root,k);
        root=merge(merge(s.first,new node(x)),s.second);
    }
    int erase(int k){
        pair<node *,node *>s1,s2;
        int ret;
        s1=split(root,k);
        s2=split(s1.second,1);
        ret=s2.first->val;
        root=merge(s1.first,s2.second);
        return ret;
    }

    int sum(int l,int r){
        pair<node *,node *>s1,s2;
        int ret;
        s1=split(root,l);
        s2=split(s1.second,r-l);
        ret=s2.first->sum;
        root=merge(merge(s1.first,s2.first),s2.second);
        return ret;
    }
};

int N,Q;
RBST L,R;

signed main(){
    cin>>N>>Q;
    for(int i=0;i<N;i++){
        L.insert(i,0);
        R.insert(i,0);
    }

    while(Q--){
        char type;
        int x,y;
        cin>>type>>x>>y;
        if(type=='L'){
            int val=L.erase(x);
            L.insert(x,val+y);
        }
        else if(type=='R'){
            int val=R.erase(x);
            R.insert(x,val+y);
        }
        else{
            cout<<L.sum(x,y)+R.sum(x,y)<<endl;
        }
        int l=L.erase(0);
        int r=R.erase(N-1);
        L.insert(N-1,r);
        R.insert(0,l);
    }
    return 0;
}
0