#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pld;
struct seg_tree {
struct node {
int left = 0;
int right = 0;
int range_sz() { return right - left; }
bool touches(int l, int r) { return left < r && l < right; }
ll sum;
ll min_prefix;
ll min_suffix;
ll local_ans;
};
#define MAXN 500001
node tree[4 * MAXN];
template<typename T>
void build(const vector <T> &arr) {
build(arr, 1, 0, arr.size());
}
template<typename T>
void build(const vector <T> &arr, int node, int curr_l, int curr_r) {
if (curr_l == curr_r - 1) {
tree[node].left = curr_l;
tree[node].right = curr_r;
tree[node].sum = arr[curr_l];
tree[node].min_prefix = tree[node].min_suffix = min((ll) 0, arr[curr_l]);
tree[node].local_ans = (arr[curr_l] == 1 ? 0 : 1);
return;
}
int curr_m = curr_l + (curr_r - curr_l) / 2;
build(arr, 2 * node, curr_l, curr_m);
build(arr, 2 * node + 1, curr_m, curr_r);
pull_index(node);
}
inline void pull_index(int node_in) {
tree[node_in] = pull(tree[node_in * 2], tree[node_in * 2 + 1]);
}
node pull(node left, node right) {
node ans;
ans.left = left.left;
ans.right = right.right;
ans.sum = left.sum + right.sum;
ans.min_prefix = min(left.min_prefix, left.sum + right.min_prefix);
ans.min_suffix = min(right.min_suffix, left.min_suffix + right.sum);
ans.local_ans = max(
abs(left.min_prefix) + abs(right.min_suffix),
max(
// abs(left.min_prefix) + max(0ll, abs(right.min_prefix) -
// (left.sum +
// abs(left.min_prefix))),
// abs(right.min_suffix) + max(0ll, abs(left.min_suffix) -
// (right.sum +
// abs(right.min_suffix)))
left.local_ans - right.sum,
-left.sum + right.local_ans
)
);
return ans;
}
ll query(int query_l, int query_r) {
return query(query_l, query_r, 1).local_ans;
}
node query(int query_l, int query_r, int node) {
if (query_l <= tree[node].left && tree[node].right <= query_r) {
return tree[node];
}
bool touches_left = tree[2 * node].touches(query_l, query_r);
bool touches_right = tree[2 * node + 1].touches(query_l, query_r);
if (!touches_right) return query(query_l, query_r, 2 * node);
else if (!touches_left)return query(query_l, query_r, 2 * node + 1);
else {
return pull(
query(query_l, query_r, 2 * node),
query(query_l, query_r, 2 * node)
);
}
}
};
seg_tree segtree;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n;
cin >> n;
string str;
cin >> str;
vector <ll> arr(n);
for (int i = 0; i < n; i++) arr[i] = (str[i] == 'C' ? 1 : -1);
segtree.build(arr);
ll q;
cin >> q;
while (q--) {
ll a, b;
cin >> a >> b;
a--;
cout << segtree.query(a, b) << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
78680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
78680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
78680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
