#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
int n,q;
int pref[500005];
int mn[500005][20];
int suff[500005];
int mn2[500005][20];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
string s;
cin>>s;
for(int i=1;i<=n;i++){
pref[i]=pref[i-1];
if(s[i-1]=='C')pref[i]++;
else pref[i]--;
mn[i][0]=pref[i];
}
for(int i=n;i;i--){
suff[i]=suff[i+1];
if(s[i-1]=='C')suff[i]++;
else suff[i]--;
mn2[i][0]=suff[i];
}
for(int j=1;j<20;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
mn2[i][j]=min(mn2[i][j-1],mn2[i+(1<<(j-1))][j-1]);
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
int ans=0;
int cnt=0;
for(int i=l-1;i<r;i++){
if(s[i]=='C')cnt++;
else cnt--;
umin(ans,cnt);
}
cnt=0;
for(int i=r-1;i>l;i--){
if(s[i]=='C')cnt++;
else cnt--;
umin(ans,cnt);
}
cout<<-ans<<'\n';
/*
int len=__lg(r-l+1);
int m=min(min(mn[l][len],mn[r-(1<<len)+1][len])-pref[l-1],min(mn2[l][len],mn2[r-(1<<len)+1][len])-suff[r+1]);
umin(m,0);
cout<<-m<<'\n';*/
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
