#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct segtree{
struct node{
int sum=0, minpref=0, id=0;
node operator+(node b){
node ans;
ans.sum = sum + b.sum;
if (sum + b.minpref < minpref){
ans.minpref = sum + b.minpref;
ans.id = b.id;
}else{
ans.minpref = minpref;
ans.id = id;
}
return ans;
}
};
int n;
vector<node> a;
segtree(vi b){
n = 1;
while(n < sz(b)) n*=2;
a.resize(n*2);
rep(i,0,sz(b)){
if (b[i]<=0) a[n+i] = {b[i],b[i],i};
else a[n+i] = {b[i],0,i-1};
}
for (int i = n-1; i>0; --i) a[i] = a[i*2]+a[i*2+1];
}
node query(int id, int l, int r, int ql, int qr){
if (l >= ql and r <= qr) return a[id];
else if (r <= ql or l >= qr) return {};
else{
int mid = (l+r)/2;
return query(id*2,l,mid,ql,qr)+query(id*2+1,mid,r,ql,qr);
}
}
node get(int l, int r){
return query(1,0,n,l,r);
}
};
int main(){
cin.tie(NULL),cin.sync_with_stdio(false);
int n,q; cin >> n;
string s; cin >> s;
vi a(n),b;
rep(i,0,n) a[i] = (s[i]=='C')?1:-1;
b = a;
reverse(all(b)); // i -> n-1-i
segtree LtoR(a), RtoL(b);
cin >> q;
while(q--){
int l,r; cin >> l >> r; // [l,r]
l--,r--;
// LtoR : l r+1
// RtoL : n-1-r n-l
auto ansL = LtoR.get(l,r+1), ansR = RtoL.get(n-1-r,n-l);
int L = n-1-ansR.id, R = ansL.id;
if (L > R) cout << max(0,-ansR.minpref)+max(0,-ansL.minpref) << '\n';
else{
auto ansL2 = LtoR.get(l,L);
cout << max(0,-ansL2.minpref)+max(0,-ansR.minpref) << '\n';
}
}
}
/*
1 1
CCCTTTTTTCC
3
1 11
4 9
1 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
