Submission #69522

# Submission time Handle Problem Language Result Execution time Memory
69522 2018-08-21T07:21:14 Z vanogam Election (BOI18_election) C++14
0 / 100
9 ms 632 KB
#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=i-1;
        if(val-=1) it->mns=-1,it->i2=l,it->i1=i-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->mns<<"("<<it->L->mns<<" "<<it->sum<<" "<<it->R->mns<<")"<<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> > p1=get1(root,0,n,f-1,g);
        pair<int,pair<int,int> > p2=get2(root,0,n,f-1,g);
        //cout<<p1.first<<" "<<p1.second.first<<" "<<p1.second.second<<endl;
        //cout<<p2.first<<" "<<p2.second.first<<" "<<p2.second.second<<endl;
        if(p1.second.first<p2.second.first) cout<<-p1.first+max(0,p2.first-p2.second.second);
        else    cout<<max(-p1.first,p2.first-p2.second.second);
        cout<<endl;
    }
}

Compilation message

election.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -