이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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; }
// todo fill ... fields stored on each interval
ll sum;
ll min_prefix;
ll min_suffix;
ll local_ans;
};
#define MAXN 200001
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) {
tree[node].left = curr_l;
tree[node].right = curr_r;
if (curr_l == curr_r - 1) {
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);
tree[node] = pull(tree[node * 2], tree[node * 2 + 1]);
tree[node].left = curr_l;
tree[node].right = curr_r;
}
node pull(node left, node right) {
node ans;
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)))
)
);
return ans;
}
void push(int node) {
if (tree[node].range_sz() == 0) return;
}
ll query(int query_l, int query_r) {
return query < 0, node > (query_l, query_r, 1).local_ans;
}
template<int OPERATION, typename DATA>
DATA query(int query_l, int query_r, int node) {
push(node);
if (!(tree[node].touches(query_l, query_r))) throw "err";
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 < OPERATION, DATA > (query_l, query_r, 2 * node);
else if (!touches_left)return query < OPERATION, DATA > (query_l, query_r, 2 * node + 1);
else {
DATA left(query < OPERATION, DATA > (query_l, query_r, 2 * node));
DATA right(query < OPERATION, DATA > (query_l, query_r, 2 * node + 1));
return pull(left, right);
}
}
};
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |