This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MX = 5e5 + 5;
struct node {
int sum, ans, mn, mx;
node() {
sum = 0, ans = 0, mn = 0, mx = 0;
}
node(int a, int b, int c, int d):
sum(a), ans(b), mn(c), mx(d)
{
}
} seg[4 * MX];
node comb(node &a, node &b) {
node ret;
ret.sum = a.sum+b.sum;
ret.mn = min(a.mn, b.mn + a.sum);
ret.mx = max(a.mx, b.mx + a.sum);
ret.ans = max({a.ans - b.sum, b.ans-a.sum, b.mx + a.sum - a.mn - ret.sum});
return ret;
}
int sz = 1;
void build(string &s, int n, int x=0, int lx=0, int rx=sz) {
if(rx-lx==1) {
if(lx<n) {
if(s[lx]=='C') seg[x] = node(1, -1, 0, 1);
else seg[x] = node(-1, 1, -1, 0);
}
else seg[x] = node();
return;
}
int m = (lx+rx)/2;
build(s, n, 2*x+1, lx, m), build(s, n, 2*x+2, m, rx);
seg[x] = comb(seg[2*x+1], seg[2*x+2]);
}
node query(int l, int r,int x=0, int lx=0, int rx=sz) { //[l, r)
if(lx>=r || rx<=l) return node();
if(lx>=l && rx<=r) return seg[x];
int m = (lx+rx)/2;
node a = query(l, r, 2*x+1, lx, m), b = query(l, r, 2*x+2, m, rx);
return comb(a, b);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
while(sz<n) sz*=2;
string s; cin >> s;
build(s, n);
int q; cin >> q;
while(q--) {
int l, r; cin >> l >> r;
--l, --r;
node x = query(l, r+1);
cout << max(0, x.ans) << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |