Submission #69526

#	Time	Username	Problem	Language	Result	Execution time	Memory
69526		vanogam	Election (BOI18_election)	C++14	0 / 100	9 ms	508 KiB

election

#include<bits/stdc++.h>
using namespace std;
int a,s,d,f,g,h,j,k,l,i,n,m,inf=1000000000;
string x;
struct tre{
    int mxs;
    int i1;
    int mns;
    int i2;
    int sum;
    tre *L;
    tre *R;
    tre(){
        mxs=0;
        mns=0;
        sum=0;
        L=NULL;
        R=NULL;
    }
};
tre *root;
void add(tre *&it,int l,int r,int idx,int val){
    if(!it) it=new tre();
    if(l>idx || r<=idx) return;
    if(l+1==r) {
        it->sum=val;
        if(val==1) it->mxs=1,it->i1=l,it->i2=l-1;
        if(val==-1) it->mns=-1,it->i2=l,it->i1=l-1;
        return;
    }
    add(it->L,l,(l+r)/2,idx,val);
    add(it->R,(l+r)/2,r,idx,val);
    it->sum=it->L->sum+it->R->sum;
    if(it->L->mxs>it->L->sum+it->R->mxs) {it->mxs=it->L->mxs;it->i1=it->L->i1;}
    else {it->mxs=it->L->sum+it->R->mxs;it->i1=it->R->i1;}

    if(it->L->mns<=it->L->sum+it->R->mns) {it->mns=it->L->mns;it->i2=it->L->i2;}
    else {it->mns=it->L->sum+it->R->mns;it->i2=it->R->i2;}
    //cout<<l<<" "<<r<<" "<<it->mxs<<"("<<it->L->mxs<<" "<<it->sum<<" "<<it->R->mxs<<" "<<it->i1<<" "<<it->R->i1<<")"<<endl;
}

pair<int,pair<int,int> > get1(tre *&it,int l,int r,int lf,int rg){
    if(!it || l>=rg || r<=lf) return {0,{l-1,0}};
    if(l>=lf && r<=rg) return {it->mns,{it->i2,it->sum}};
    pair<int,pair<int,int> > p1=get1(it->L,l,(l+r)/2,lf,rg);
    pair<int,pair<int,int> > p2=get1(it->R,(l+r)/2,r,lf,rg);

    p2.second.second+=p1.second.second;

    //cout<<"  "<<l<<" "<<r<<": "<<p1.first<<" "<<p2.first<<" "<<p1.second.second<<endl;
    if(p1.first<=p1.second.second+p2.first) {p1.second.second=p2.second.second;return p1;}
    else {
        p2.first+=p1.second.second;
        return p2;
    }

}
pair<int,pair<int,int> > get2(tre *&it,int l,int r,int lf,int rg){
    if(!it || l>=rg || r<=lf) return {0,{l-1,0}};
    if(l>=lf && r<=rg) return {it->mxs,{it->i1,it->sum}};
    pair<int,pair<int,int> > p1=get2(it->L,l,(l+r)/2,lf,rg);
    pair<int,pair<int,int> > p2=get2(it->R,(l+r)/2,r,lf,rg);
    p2.second.second+=p1.second.second;

    if(p1.first>p1.second.second+p2.first) {p1.second.second=p2.second.second;return p1;}
    else {
        p2.first+=p1.second.second;
        return p2;
    }
}
main(){
    ios::sync_with_stdio(0);
    cin>>n>>x;
    for(i=0;i<n;i++){
        if(x[i]=='C') add(root,0,n,i,1); else add(root,0,n,i,-1);
    }
    cin>>m;
    for(i=0;i<m;i++){
        cin>>f>>g;
        pair<int,pair<int,int> > p2=get2(root,0,n,f-1,g);
        pair<int,pair<int,int> > p1=get1(root,0,n,f-1,p2.second.first+1);
        pair<int,pair<int,int> > p3=get1(root,0,n,p2.second.first+1,g);
        p3.first+=p1.second.second;
        //cout<<p1.first<<" "<<p1.second.first<<" "<<p1.second.second<<endl;
        //cout<<p2.first<<" "<<p2.second.first<<" "<<p2.second.second<<endl;
        //cout<<p3.first<<" "<<p3.second.first<<" "<<p3.second.second<<endl;
        //k=min(p1.first,p1.second.second+p3.first);
        cout<<-p1.first+max(-p3.first,p2.first-p2.second.second)<<endl;
    }
}

Compilation message (stderr)

election.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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