#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];
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]);
}
}
void update1(int nod , int l , int r , int pos , int val){
if(l > r)return ;
if(pos <= r && pos >= l){
st1[nod] = max(st1[nod],val);
int mid = (l+r)/2;
update1(2*nod ,l ,mid,pos,val);
update1(2*nod+1,mid+1,r ,pos,val);
}
return ;
}
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));
}
void update2(int nod , int l , int r , int pos , int val){
if(l > r)return ;
if(pos <= r && pos >= l){
st2[nod] = max(st2[nod],val);
}else{
return ;
}
int mid = (l+r)/2;
update2(2*nod,l,mid,pos,val);
update2(2*nod+1,mid+1,r,pos,val);
}
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 l, r;
for(int i = 1 ;i <= n ;i++){
cin >> l >> r;
int v1 = query1(1,l,r,1,n);
int v2 = query2(1,l,r,1,n);
cout << max(v1 - p1[l-1],v2-p2[r+1]);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
