#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
#define her cerr<<"here"<<endl;
const int N = 7e5 + 5;
const int B = 267;
int a[N], pref[N], suff[N], mx[2][B + 1], in[B][B + 1][B + 1];
int pos[B][B + 1], sos[B][B + 1], used[N];
int pv[B], sv[B];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
string s; cin >> s;
for(int b=0;b * B<n;b++){
int l = b * B, r = min(n, (b + 1) * B);
memset(pos[b], -1, sizeof pos[b]);
for(int i=l;i<r;i++){
if(s[i] == 'C') pref[i]--;
else pref[i]++;
pref[i + 1] = pref[i];
mx[0][b] = max(mx[0][b], pref[i]);
if(pref[i] > 0 && pos[b][pref[i]] == -1) pos[b][pref[i]] = i;
}
memset(sos[b], -1, sizeof sos[b]);
for(int i=r-1;i>=l;i--){
suff[i] = suff[i + 1];
if(s[i] == 'C') suff[i]--;
else suff[i]++;
mx[1][b] = max(mx[1][b], suff[i]);
if(suff[i] > 0 && sos[b][suff[i]] == -1) sos[b][suff[i]] = i;
}
for(int i=mx[0][b];i>0;i--){
int cc = 0, r = mx[0][b];
for(int j=mx[1][b];j>0;j--){
if(r > 0 && sos[b][j] <= pos[b][r]) cc++, r--;
in[b][i][j] = cc;
}
}
}
int q; cin >> q;
for(int i=0;i<q;i++){
int l, r; cin >> l >> r;
l--, r--;
int l_ = l / B, r_ = r / B;
if(l_ == r_){
int sum = 0, x = 1, cnt = 0;
for(int i=l;i<=r;i++){
if(s[i] == 'C') sum--;
else sum++;
if(sum == x) used[i] = 1, cnt++, x++;
}
int is = 0; sum = 0, x = 1;
for(int i=r;i>=l;i--){
if(s[i] == 'C') sum--;
else sum++;
if(used[i]) is++, used[i] = 0;
if(sum == x){
if(!is) cnt++;
else is--;
x++;
}
}
cout<<cnt<<"\n";
for(int i=l;i<=r;i++) used[i] = 0;
continue;
}
int sum = 0, x = 1, cnt = 0;
for(int i=l;i<(l_ + 1) * B;i++){
if(s[i] == 'C') sum--;
else sum++;
if(sum == x) used[i] = 1, cnt++, x++;
}
for(int b=l_+1;b<r_;b++){
if(mx[0][b] >= x - sum){
pv[b] = x - sum;
x += (mx[0][b] - x + sum + 1);
} else {
pv[b] = mx[0][b] + 1;
}
sum += suff[b * B];
}
for(int i=r_ * B;i<=r;i++){
if(s[i] == 'C') sum--;
else sum++;
if(sum == x) used[i] = 1, cnt++, x++;
}
int is = 0;
sum = 0, x = 1;
for(int i=r;i>=r_*B;i--){
if(s[i] == 'C') sum--;
else sum++;
if(used[i]) is++, used[i] = 0;
if(sum == x){
if(!is) cnt++;
else is--;
x++;
}
used[i] = 0;
}
for(int b=r_-1;b>l_;b--){
if(mx[1][b] >= x - sum){
sv[b] = x - sum;
x += (mx[1][b] - x + sum + 1);
} else {
sv[b] = mx[1][b] + 1;
}
cnt += mx[0][b] - pv[b] + 1; // in[b][pv[b]][sv[b]];
is += in[b][pv[b]][sv[b]];
if(is >= (mx[1][b] - sv[b] + 1)) is -= (mx[1][b] - sv[b] + 1);
else {
cnt += (mx[1][b] - sv[b] + 1 - is);
is = 0;
}
is += (mx[0][b] - pv[b] + 1 - in[b][pv[b]][sv[b]]);
sum += suff[b * B];
}
for(int i=(l_ + 1) * B - 1;i>=l;i--){
if(s[i] == 'C') sum--;
else sum++;
if(used[i]) is++, used[i] = 0;
if(sum == x){
if(!is) cnt++;
else is--;
x++;
}
used[i] = 0;
}
cout<<cnt<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
