Submission #1209784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209784		Newtonabc	Election (BOI18_election)	C++20	100 / 100	807 ms	20408 KiB

election

#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
string st;
struct node{
    int ans,mxl,mxr,sum;
    friend node operator+(const node &a,const node &b){
        node ret;
        if(a.ans==-1e9){ret=b; return ret;}
        if(b.ans==-1e9){ret=a; return ret;}
        ret.sum=a.sum+b.sum;
        ret.mxl=max({0,a.mxl,b.mxl+a.sum});
        ret.mxr=max({0,a.mxr+b.sum,b.mxr});
        ret.ans=max({a.ans+b.sum,a.sum+b.ans,a.mxl+b.mxr});
        return ret;
    }
    void pt(){
        cout<<ans <<" " <<mxl <<" " <<mxr <<" " <<sum <<" ";
    }
}s[N],out;
void build(int l,int r,int idx){
    if(l==r){
        if(st[l]=='C'){
            s[idx].sum=s[idx].ans=-1;
            s[idx].mxl=s[idx].mxr=0;
        }
        else{
            s[idx].sum=s[idx].ans=1;
            s[idx].mxl=s[idx].mxr=1;
        }
        // cout<<l <<" " <<r <<" ";
        // s[idx].pt();
        // cout<<"\n";
        return;
    }
    int m=(l+r)/2;
    build(l,m,idx*2);
    build(m+1,r,idx*2+1);
    s[idx]=s[idx*2]+s[idx*2+1];
    // cout<<l <<" " <<r <<" ";
    // s[idx].pt();
    //cout<<"\n";
}
node query(int l,int r,int idx,int a,int b){
    if(b<l || a>r) return out;
    if(a<=l && b>=r) return s[idx];
    int m=(l+r)/2;
    return query(l,m,idx*2,a,b)+query(m+1,r,idx*2+1,a,b);
}
int main(){
    int n,q;
    out.ans=-1e9;
    cin>>n >>st >>q;
    build(0,n-1,1);
    while(q--){
        int a,b;
        cin>>a >>b;
        node tmp=query(0,n-1,1,a-1,b-1);
        int ans=0;
        ans=max(ans,tmp.ans);
        cout<<ans <<"\n";
    }
}

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