#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n, q;
int s[500005];
int st1[2000005],st2[2000005];
int p1[500005],p2[500005];
vector <int> vec;
void build1(int nod , int l , int r){
if(l == r){
st1[nod] = p1[l];
}else{
int mid = (l+r)/2;
build1(nod*2,l,mid);
build1(nod*2+1,mid+1,r);
st1[nod] = max(st1[nod*2],st1[nod*2+1]);
}
}
void build2(int nod , int l , int r){
if(l == r){
st2[nod] = p2[l];
}else{
int mid = (l+r)/2;
build2(nod*2,l,mid);
build2(nod*2+1,mid+1,r);
st2[nod] = max(st2[nod*2],st2[nod*2+1]);
}
}
int query1(int nod , int l , int r , int lt , int rt){
if(l > r)return 0;
if(l >= lt && r <= rt)return st1[nod];
int mid = (l+r)/2;
return max(query1(nod*2,l,mid,lt,rt),query1(nod*2+1,mid+1,r,lt,rt));
}
int query2(int nod , int l , int r , int lt , int rt){
if(l > r)return 0;
if(l >= lt && r <= rt)return st2[nod];
int mid = (l+r)/2;
return max(query2(nod*2,l,mid,lt,rt),query2(nod*2+1,mid+1,r,lt,rt));
}
int main(){
cin >> n;
for(int i = 1; i <= n ; i++){
char ch;
cin >> ch;
if(ch == 'C')s[i]=-1;
else s[i]=1;
}
for(int i = 1; i <= 4*n ; i++){
st1[i] = -1e9;
st2[i] = -1e9;
}
int sum = 0;
for(int i = 1 ; i <= n; i++){
sum += s[i];
p1[i] = sum;
}
build1(1,1,n);
sum = 0;
for(int i = n ; i > 0; i--){
sum += s[i];
p2[i]=sum;
}
build2(1,1,n);
cin >> q;
int li, ri;
for(int i = 1 ;i <= q ;i++){
cin >> li >> ri;
int v1 = query1(1,li,ri,1,n);
int v2 = query2(1,li,ri,1,n);
cout << max(0,max(v1 - p1[li-1],v2-p2[ri+1])) << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
