#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);
ret.mx = max(a.mx, b.mx);
ret.ans = max({a.ans, b.ans-a.sum, b.mx + a.sum - a.mn - ret.sum});
return ret;
}
int sz = 1;
void build(string &s, int x=0, int lx=0, int rx=sz) {
if(rx-lx==1) {
if(lx<s.size()) {
if(s[lx]=='C') seg[x] = node(1, -1, 1, 1);
else seg[x] = node(-1, 1, -1, -1);
}
else seg[x] = node();
return;
}
int m = (lx+rx)/2;
build(s, 2*x+1, lx, m), build(s, 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);
int q; cin >> q;
while(q--) {
int l, r; cin >> l >> r;
--l, --r;
int ans = 0;
int mn = 0;
int sum =0;
for(int i=l;i<=r;i++) {
if(s[i]=='C') sum++;
else --sum;
}
int curr = 0;
for(int i=l;i<=r;i++) {
if(s[i]=='C') ++curr;
else --curr;
mn = min(mn, curr);
ans = max(ans, curr-mn-sum);
}
node x = query(l, r+1);
cout << max(0, x.ans) << "\n";
}
}
Compilation message
election.cpp: In function 'void build(std::string&, int, int, int)':
election.cpp:25:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if(lx<s.size()) {
| ~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
31596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
31596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
31596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
