#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define ll long long
struct Node{
ll sum, pref, suff, ans;
};
int n, arr[(int)5e5 + 10];
struct SegmentTree{
vector<Node> sgt;
SegmentTree(int n){
sgt.resize(4 * n);
}
Node merge(Node a, Node b){
return { a.sum + b.sum, max(a.pref, a.sum + b.pref), max(b.suff, a.suff + b.sum),
max({0LL, a.pref + b.suff}) };
}
void build(int k = 1, int l = 0, int r = n - 1){
if(l == r){
sgt[k] = { arr[l], max(0, arr[l]), max(0, arr[l]), max(arr[l], 0) };
return;
}
int m = (l + r) / 2;
build(k * 2, l, m);
build(k * 2 + 1, m + 1, r);
sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
}
Node get(int k, int l, int r, int i, int j){
if (l > j || r < i) return {0, 0, 0, 0};
if (i <= l && r <= j) return sgt[k];
int m = (l + r) / 2;
return merge(get(k * 2, l, m, i, j), get(k * 2 + 1, m + 1, r, i, j));
}
} sgt(5e5);
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
string s;
cin >> s;
for (int i = 0; i < n; i++) arr[i] = (s[i] == 'C' ? -1 : 1);
sgt.build();
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << sgt.get(1, 0, n - 1, --x, --y).ans << '\n';
}
}
Compilation message
election.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
43 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
63064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
63064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
63064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
