#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 500000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;
struct node{
int mn, mx, Rmx, Lmn;
};
node seg[N << 2];
int n, q, ps[N], ted[N];
string s;
node merge(node x, node y){
node res = x;
res.mx = y.mx, res.Rmx = y.Rmx;
if (res.mn > y.mn) res.mn = y.mn, res.Lmn = y.Lmn;
if (x.mx > res.mx) res.mx = x.mx, res.Rmx = x.Rmx;
return res;
}
void build(int id, int l, int r){
if (r - l == 1){
seg[id].mn = seg[id].mx = ps[l], seg[id].Rmx = seg[id].Lmn = l;
return;
}
int md = (l + r) >> 1;
build(id << 1, l, md);
build(id << 1 | 1, md, r);
seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}
node get(int id, int lq, int rq, int l, int r){
if (rq <= l || r <= lq){
node res;
res.mx = -INF, res.mn = INF;
return res;
}
if (lq <= l && r <= rq) return seg[id];
int md = (l + r) >> 1;
return merge(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}
int SZ(int L, int R, int LL, int RR){
int l = max(L, LL), r = min(R, RR);
if(r < l) return 0;
return ted[r] - ted[l - 1];
}
pii baze(int L, int R, int LL, int RR){
int l = max(L, LL), r = min(R, RR);
return {l,r};
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s;
for (int i = 1; i <= n; i++){
ted[i] = ted[i - 1];
if (s[i - 1] == 'C') ps[i] = ps[i - 1] + 1;
else ps[i] = ps[i - 1] - 1, ted[i]++;
}
build(1, 0, n + 1);
cin >> q;
//cout <<seg[1].mx << ' ' << seg[1].mn << '\n';
for (int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
node res = get(1, l - 1, r + 1, 0, n + 1);
int L, R;
int ans = 0;
if (res.mx <= ps[r]) L = n + 1, R = n + 1;
else L = res.Rmx + 1, R = r;
//ans += res.mx - ps[r];
int LL, RR;
if (res.mn >= ps[l - 1]) LL = 0, RR = 0;
else LL = l, RR = res.Lmn;
//ans += ps[l - 1] - res.mn;
//cout << ans << '\n';
//cout << L << ' ' << R << ' ' << LL << ' ' << RR << '\n';
int x = SZ(L, R, LL, RR);
//cout << x << '\n';
int val1 = res.mx - ps[r], val2 = ps[l - 1] - res.mn;
if (x == 0){
ans += val1 + val2;
cout << ans << '\n';
continue;
}
pii Now = baze(L, R, LL, RR);
res = get(1, Now.S, r + 1, 0, n + 1);
val1 -= max(0, res.mx - ps[r]);
res = get(1, l - 1, Now.F, 0, n + 1);
val2 -= max(0, ps[l - 1] - res.mn);
ans += min({val1, val2, x});
ans += (val1 - ans) + (val2 - ans);
cout << ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
