結果

問題 No.1802 Range Score Query for Bracket Sequence
ユーザー ytftytft
提出日時 2022-02-14 22:45:24
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,935 bytes
コンパイル時間 3,454 ms
コンパイル使用メモリ 251,316 KB
実行使用メモリ 6,844 KB
最終ジャッジ日時 2023-09-11 16:49:04
合計ジャッジ時間 10,364 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 WA -
testcase_02 WA -
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 AC 1 ms
4,376 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 RE -
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct segment_tree{
    vector<T> tree;
    int depth;
    function<T(T,T)> comp;
    T unit;
    segment_tree(vector<T>& a,function<T(T,T)> f,T unit=0){
        this->unit=unit;
        comp=f;
        depth=(int)ceil(log(a.size())/log(2))+1;
        tree.resize((1<<depth)-1);
        fill(tree.begin()+(1<<(depth-1)-1),tree.end(),unit);
        copy(a.begin(),a.end(),tree.begin()+((1<<(depth-1))-1));
        for(int i=(1<<(depth-1))-2;i>=0;--i){
            tree[i]=comp(tree[i*2+1],tree[i*2+2]);
        }
    }
    void update(int index,T value){
        index+=(1<<(depth-1))-1;
        tree[index]=value;
        while(index!=0){
            index=(index-1)/2;
            tree[index]=comp(tree[index*2+1],tree[index*2+2]);
        }
    }
    T get(int begin,int end){
        T ret=unit;
        begin+=(1<<(depth-1))-1;
        end+=(1<<(depth-1))-1;
        while(begin<end){
            if(begin%2==0){
                ret=comp(ret,tree[begin]);
            }
            begin/=2;
            if(end%2==0){
                ret=comp(ret,tree[end-1]);
            }
            end=(end-1)/2;
        }
        return ret;
    }
};

int main(){
	int N,Q,q;
    string S;
    cin>>N>>Q>>S;
    vector<int> array(N-1,0);
    segment_tree<int> T(array,[](int a,int b){return a+b;},0);
    for(int i=0;i<N-1;++i){
        if((S[i]=='(')&&(S[i+1]==')')){
            T.update(i,1);
        }
    }
    for(int i=0;i<Q;++i){
        cin>>q;
        if(q==1){
            cin>>q;
            S[q-1]=(S[q-1]=='('?')':'(');
            for(int i=max(0,q-2);i<min(q,N-1);++i){
                if((S[i]=='(')&&(S[i+1]==')')){
                    T.update(i,1);
                }else{
                    T.update(i,0);
                }
            }
        }else{
            int l,r;
            cin>>l>>r;
            cout<<T.get(l-1,r)<<endl;
        }
    }
}
0