Submission #1178203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178203		AlgorithmWarrior	Election (BOI18_election)	C++20	100 / 100	839 ms	19760 KiB

election

#include <bits/stdc++.h>

using namespace std;

int const MAX=500005;

struct node{
    int rez,ult,maxim,minim;
};

struct AINT{
    int n;
    node v[4*MAX];
    node combine(node a,node b){
        return {
            .rez=max(max(a.rez,b.rez),b.maxim+a.ult-a.minim),
            .ult=a.ult+b.ult,
            .maxim=max(a.maxim,b.maxim+a.ult),
            .minim=min(a.minim,b.minim+a.ult)
        };
    }
    void update(int nod,int st,int dr,int poz,int val){
        if(st==dr)
            v[nod]={0,val,val,val};
        else{
            int mij=(st+dr)/2;
            if(poz<=mij)
                update(2*nod,st,mij,poz,val);
            else
                update(2*nod+1,mij+1,dr,poz,val);
            v[nod]=combine(v[2*nod],v[2*nod+1]);
        }
    }
    node query(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod];
        node ans={0,0,0,0};
        int mij=(st+dr)/2;
        if(a<=mij)
            ans=combine(ans,query(2*nod,st,mij,a,b));
        if(b>mij)
            ans=combine(ans,query(2*nod+1,mij+1,dr,a,b));
        return ans;
    }
}aint;

void read(){
    cin>>aint.n;
    int i;
    for(i=1;i<=aint.n;++i){
        char ch;
        cin>>ch;
        if(ch=='C')
            aint.update(1,1,aint.n,i,1);
        else
            aint.update(1,1,aint.n,i,-1);
    }
}

void process_queries(){
    int q;
    cin>>q;
    int i;
    for(i=1;i<=q;++i){
        int st,dr;
        cin>>st>>dr;
        node ans=aint.query(1,1,aint.n,st,dr);
        cout<<max(ans.rez,ans.maxim)-ans.ult<<'\n';
    }
}

int main()
{
    read();
    process_queries();
    return 0;
}

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