Submission #858301

#	Time	Username	Problem	Language	Result	Execution time	Memory
858301		Warinchai	Election (BOI18_election)	C++14	0 / 100	7 ms	31576 KiB

election

#include<bits/stdc++.h>
using namespace std;
char ar[500005];
int n;
struct segtree{
    struct node{
        int pre,suf,sc,st;
        node(char x=' '){
            if(x=='C'){
                pre=0;
                suf=0;
                sc=1;
                st=0;
            }else if(x=='T'){
                pre=1;
                suf=1;
                sc=0;
                st=1;
            }else{
                pre=suf=sc=st=0;
            }
        }
        friend node operator+(node a,node b){
            node c;
            c.pre=max(a.pre,a.pre+b.pre-(a.sc-(a.st-a.pre)));
            c.suf=max(b.suf,b.suf+a.suf-(b.sc-(b.st-b.suf)));
            c.sc=a.sc+b.sc;
            c.st=a.st+b.st;
            return c;
        }
    };
    node info[2000005];
    void build(int st,int en,int i){
        if(st==en){
            node x(ar[st]);
            info[i]=x;
            //cout<<st<<" "<<en<<":\n";
            //cout<<info[i].pre<<" "<<info[i].suf<<" "<<info[i].sc<<" "<<info[i].st<<"\n";
            return;
        }
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
        //cout<<st<<" "<<en<<":\n";
        //cout<<info[i].pre<<" "<<info[i].suf<<" "<<info[i].sc<<" "<<info[i].st<<"\n";
    }
    node fans(int st,int en,int i,int l,int r){
        if(st>r||en<l){
            return node();
        }
        if(st>=l&&en<=r){
            return info[i];
        }
        int m=(st+en)/2;
        return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
    }
    int fans(int l,int r){
        node x=fans(1,n,1,l,r);
        return max(x.pre,x.suf);
    }
}tr;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    string s;
    cin>>s;
    for(int i=1;i<=n;i++){
        ar[i]=s[i-1];
    }
    int m;
    cin>>m;
    tr.build(1,n,1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        cout<<tr.fans(a,b)<<"\n";
    }
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18