結果

問題 No.2992 Range ABCD String Query
ユーザー kotatsugame
提出日時 2024-12-25 10:13:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 264 ms / 6,000 ms
コード長 1,340 bytes
コンパイル時間 958 ms
コンパイル使用メモリ 78,908 KB
実行使用メモリ 32,000 KB
最終ジャッジ日時 2024-12-25 10:13:35
合計ジャッジ時間 13,458 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
#include<cassert>
#include<atcoder/segtree>
using namespace std;
struct dat{
    int a,ab,abc,abcd,b,bc,bcd,c,cd,d;
};
dat op(dat l,dat r)
{
    dat ret;
    ret.a=l.a+r.a;
    ret.ab=min(l.a+r.ab,l.ab+r.b);
    ret.abc=min({l.a+r.abc,l.ab+r.bc,l.abc+r.c});
    ret.abcd=min({l.a+r.abcd,l.ab+r.bcd,l.abc+r.cd,l.abcd+r.d});
    ret.b=l.b+r.b;
    ret.bc=min(l.b+r.bc,l.bc+r.c);
    ret.bcd=min({l.b+r.bcd,l.bc+r.cd,l.bcd+r.d});
    ret.c=l.c+r.c;
    ret.cd=min(l.c+r.cd,l.cd+r.d);
    ret.d=l.d+r.d;
    return ret;
}
dat e(){return(dat){};}
dat INIT[4];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    {//a
        dat v={};
        v.b=v.bc=v.bcd=v.c=v.cd=v.d=1;
        v.a=v.ab=v.abc=v.abcd=0;
        INIT[0]=v;
    }
    {//b
        dat v={};
        v.a=v.c=v.cd=v.d=1;
        v.b=v.ab=v.abc=v.abcd=v.bc=v.bcd=0;
        INIT[1]=v;
    }
    {//c
        dat v={};
        v.a=v.ab=v.b=v.d=1;
        v.c=v.bc=v.abc=v.abcd=v.bcd=v.cd=0;
        INIT[2]=v;
    }
    {//d
        dat v={};
        v.a=v.ab=v.abc=v.b=v.bc=v.c=1;
        v.abcd=v.bcd=v.cd=v.d=0;
        INIT[3]=v;
    }
    int N,Q;
    string S;
    cin>>N>>Q>>S;
    vector<dat>init(N);
    for(int i=0;i<N;i++)init[i]=INIT[S[i]-'A'];
    atcoder::segtree<dat,op,e>seg(init);
    for(;Q--;)
    {
        int OP;cin>>OP;
        if(OP==1)
        {
            int x;char c;
            cin>>x>>c;
            x--;
            seg.set(x,INIT[c-'A']);
        }
        else
        {
            int l,r;cin>>l>>r;
            dat t=seg.prod(l-1,r);
            cout<<t.abcd<<"\n";
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0