#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;
const int INF = 1e9 + 2137;
template<class T> struct Seg {
T ID = INF; T comb(T a, T b) { return min(a, b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n, ID); }
void pull(int p) { seg[p] = comb(seg[2*p], seg[2*p+1]); }
void upd(int p, T val) { seg[p+=n] = val; for(p/=2; p; p/=2) pull(p); }
T query(int l, int r) {
T ra = ID, rb = ID;
for(l+=n, r+=n+1; l < r; l/=2, r/=2) {
if(l&1) ra = comb(ra, seg[l++]);
if(r&1) rb = comb(seg[--r], rb);
}
return comb(ra, rb);
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
string S;
cin>>S;
int p[n];
int s[n];
Seg<int> pref, suf;
pref.init(n);
suf.init(n);
p[0] = (S[0] == 'C' ? 1 : -1);
s[n-1] = (S[n-1] == 'C' ? 1 : -1);
pref.upd(0, p[0]);
suf.upd(n-1, s[n-1]);
for(int i=1; i<n; i++) {
p[i] = p[i-1] + (S[i] == 'C' ? 1 : -1);
pref.upd(i, p[i]);
}
for(int i=n-2; i>=0; i--) {
s[i] = s[i+1] + (S[i] == 'C' ? 1 : -1);
suf.upd(i, s[i]);
}
int q;
cin>>q;
while(q--) {
int l, r;
cin>>l>>r;
int mp = pref.query(l-1, r-1);
int ms = suf.query(l-1, r-1);
//cerr<<mp<<" - "<<ms<<"\n";
if(l != 1)
mp -= p[l-2];
if(r != n)
ms -= p[r];
int ans = min(0, min(mp, ms));
cout<<abs(ans)<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
