#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
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 |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
