#include <bits/stdc++.h>
//#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int inf = 1000000000;
int n, q, votes[500005], pref[500005], suff[500005];
struct node{
int s, e, m = (s+e)>>1, val = 0;
node *l, *r;
node(int _s, int _e): s(_s), e(_e){
if(s != e) l = new node(s, m), r = new node(m+1, e);
}
void up(int x, int v){
if(x == s and x == e) val += v;
else{
if(x <= m) l->up(x, v);
else r->up(x, v);
val = min(l->val, r->val);
}
}
int qry(int x, int y){
if(x == s and y == e) return val;
else if(y <= m) return l->qry(x, y);
else if(x > m) return r->qry(x, y);
else return min(l->qry(x, m), r->qry(m+1, y));
}
} *PREF, *SUFF;
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
PREF = new node(1, n), SUFF = new node(1, n);
for(int i = 1; i <= n; i++){
char x; cin >> x;
if(x == 'C') votes[i] = 1;
else votes[i] = -1;
pref[i] = pref[i-1] + votes[i];
PREF->up(i, pref[i]);
}
for(int i = n; i >= 1; i--) suff[i] = suff[i+1] + votes[i], SUFF->up(i, suff[i]);
cin >> q;
while(q--){
int l, r; cin >> l >> r;
int a = PREF->qry(l, r) - pref[l-1], b = SUFF->qry(l, r) - suff[r+1];
int ans = min(a, b);
if(ans > 0) ans = 0;
else ans = -ans;
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
