#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 5e5+7;
struct segment_tree
{
ll st[mxn<<2];
void update(ll id, ll l, ll r, ll u, ll x)
{
if (r < u || u < l) return;
if (l == r)
{
st[id] = (st[id]+x);
return;
}
ll m = (r+l)>>1;
update(id<<1,l,m,u,x); update(id<<1|1,m+1,r,u,x);
st[id] = min(st[id<<1],st[id<<1|1]);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
if (r < u || v < l) return 1e18;
if (u <= l && r <= v) return st[id];
ll m = (r+l)>>1;
return min(get(id<<1,l,m,u,v),get(id<<1|1,m+1,r,u,v));
}
} st1, st2;
ll dpf[mxn], dpb[mxn], n, q;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
cin >> n;
string s; cin >> s;
for (ll i = 1; i <= n; i++)
{
dpf[i] = (s[i-1] == 'C' ? 1 : -1);
dpf[i] += dpf[i-1];
st1.update(1,1,n,i,dpf[i]);
}
for (ll i = n; i >= 1; i--)
{
dpb[i] = (s[i-1] == 'C' ? 1 : -1);
dpb[i] += dpb[i+1];
st2.update(1,1,n,i,dpb[i]);
}
cin >> q;
while (q--)
{
ll l, r; cin >> l >> r;
ll opt_l = st1.get(1,1,n,l,r)-dpf[l-1], opt_r = st2.get(1,1,n,l,r)-dpb[r+1];
ll opt = min(opt_l,opt_r);
if (opt >= 0) cout << 0 << '\n';
else cout << -opt << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
