Submission #1266200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266200		warrenn	Election (BOI18_election)	C++20	100 / 100	937 ms	66540 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define int long long 

struct isi{
    int sum,pref,suf,ans;
};

string s;
vector<isi>st;

isi merg(isi a,isi b){
    // cout<<a.sum<<" "<<a.pref<<" "<<a.suf<<" "<<a.ans<<endl;
    // cout<<b.sum<<" "<<b.pref<<" "<<b.suf<<" "<<b.ans<<endl;
    isi akh;
    akh.sum=a.sum+b.sum;
    akh.pref=min(a.sum+b.pref,a.pref);
    akh.suf=min(b.sum+a.suf,b.suf);
    akh.ans=max({a.ans-(b.sum),b.ans-(a.sum),-(a.pref+b.suf)});
    //cout<<akh.sum<<" "<<akh.pref<<" "<<akh.suf<<" "<<akh.ans<<endl;
    return akh;
}

void build(int idx,int l,int r){
    if(l==r){
        if(s[l]=='C'){
            st[idx]={1,0,0,0};
        }
        else{
            st[idx]={-1,-1,-1,1};
        }
        return;
    }
    int mid=(l+r)/2;
    build(2*idx,l,mid);
    build(2*idx+1,mid+1,r);
    st[idx]=merg(st[2*idx],st[2*idx+1]);
    
}

isi query(int idx,int l,int r,int posl,int posr){
    if(l>=posl && r<=posr)return st[idx];
    if(l>posr || r<posl)return {0,0,0,0};
    int mid=(l+r)/2;
    return merg(query(2*idx,l,mid,posl,posr),query(2*idx+1,mid+1,r,posl,posr));
}

signed main(){
    int n;
    cin>>n;
    cin>>s;
    s="."+s;
    st=vector<isi>(4*n+1);
    build(1,1,n);
    int qu;
    cin>>qu;
    while(qu--){
        int l,r;
        cin>>l>>r;
        cout<<query(1,1,n,l,r).ans<<endl;
    }
}

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