#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
int n , q;
const int N = (1<<19);
struct segTree
{
vector<int> tree;
segTree(vector<int> &a)
{
tree.assign(2*N , N);
fore(i , N)
{
tree[i + N] = a[i];
}
forn(i , N - 1 , 1)
tree[i] = min(tree[2*i] , tree[2*i + 1]);
}
int query(int l , int r)
{
l+=N;
r+=N;
if(l == r)
return tree[l];
int lt = tree[l] , rt = tree[r];
while(l + 1 < r) {
if (l % 2 == 0)
lt = min(lt, tree[l + 1]);
if (r % 2 == 1)
rt = min(tree[r - 1], rt);
l>>=1;
r>>=1;
}
return min(lt , rt);
}
};
vector<int> a(N) , pref(N) , suf(N);
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
map<int , vector<int>>posPref , posSuf ;
map<int ,vector<int>> pos;
forr(i , 1 , n)
{
char c;
cin>>c;
if(c == 'C')
a[i] = 1;
else
a[i] = -1;
pos[a[i]].pb(i);
pref[i] = a[i] + pref[i - 1];
posPref[pref[i]].pb(i);
}
forn(i , n , 1)
{
suf[i] = suf[i + 1] + a[i];
}
forr(i , 1 , n)
posSuf[suf[i]].pb(i);
segTree pmin(pref) , smin(suf);
cin>>q;
while (q--)
{
int _l , _r;
cin>>_l>>_r;
if(pref[_r] - pref[_l - 1] == -(_r - _l + 1))
{
cout<<_r - _l + 1<<nl;
continue;
}
int ans = 0;
int l = *lower_bound(pos[1].begin() , pos[1].end() , _l);
ans+=l - _l;
int r = *prev(upper_bound(pos[1].begin() , pos[1].end() , _r));
ans+=_r - r;
int mp = pmin.query(l , r) - pref[l - 1];
int ms = smin.query(l , r) - suf[r + 1];
auto &v = posPref[mp + pref[l - 1]];
int i = *lower_bound(v.begin() , v.end() , l);
auto &u = posSuf[ms + suf[r + 1]];
int j = *prev(upper_bound(u.begin() , u.end() , r));
if(i < j)
ans+=abs(mp) * (mp < 0) + abs(ms) * (ms < 0);
else
ans+=max((mp < 0) * abs(mp) , (ms < 0) * abs(ms));
cout<<ans<<nl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
29272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
