#include<bits/stdc++.h>
using namespace std;
char ar[500005];
int n;
struct segtree{
struct node{
int pre,suf,sc,st;
node(char x=' '){
if(x=='C'){
pre=0;
suf=0;
sc=1;
st=0;
}else if(x=='T'){
pre=1;
suf=1;
sc=0;
st=1;
}else{
pre=suf=sc=st=0;
}
}
friend node operator+(node a,node b){
node c;
c.pre=max(a.pre,a.pre+b.pre-(a.sc-(a.st-a.pre)));
c.suf=max(b.suf,b.suf+a.suf-(b.sc-(b.st-b.suf)));
c.sc=a.sc+b.sc;
c.st=a.st+b.st;
return c;
}
};
node info[2000005];
void build(int st,int en,int i){
if(st==en){
node x(ar[st]);
info[i]=x;
//cout<<st<<" "<<en<<":\n";
//cout<<info[i].pre<<" "<<info[i].suf<<" "<<info[i].sc<<" "<<info[i].st<<"\n";
return;
}
int m=(st+en)/2;
build(st,m,i*2);
build(m+1,en,i*2+1);
info[i]=info[i*2]+info[i*2+1];
//cout<<st<<" "<<en<<":\n";
//cout<<info[i].pre<<" "<<info[i].suf<<" "<<info[i].sc<<" "<<info[i].st<<"\n";
}
node fans(int st,int en,int i,int l,int r){
if(st>r||en<l){
return node();
}
if(st>=l&&en<=r){
return info[i];
}
int m=(st+en)/2;
return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
}
int fans(int l,int r){
node x=fans(1,n,1,l,r);
return max(x.pre,x.suf);
}
}tr;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
string s;
cin>>s;
for(int i=1;i<=n;i++){
ar[i]=s[i-1];
}
int m;
cin>>m;
tr.build(1,n,1);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
cout<<tr.fans(a,b)<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
31576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
