#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
using namespace std;
int next_power_of_two(int x) { return 1LL<<(__lg(x-1)+1); }
struct Value {
int inc, dec, sum;
constexpr static Value Identity() { return {0, 0, 0}; }
static Value Single(char x) {
int val = (x == 'C') ? 1 : -1;
return {val<0, val<0, val};
}
friend Value combine(Value a, Value b) {
Value res;
res.inc = a.inc + max(0LL, (b.inc - max(0LL, a.sum)));
res.dec = b.dec + max(0LL, (a.dec - max(0LL, b.sum)));
res.sum = a.sum + b.sum;
return res;
}
};
struct Segtree {
int n;
vector<Value> tree;
Segtree(string& v) {
n = next_power_of_two(v.size());
tree.assign(2*n, Value::Identity());
build(v, 0, 0, n);
}
public:
Value query(int ql, int qr) {
assert(0 <= ql && ql < qr && qr <= n);
return query(ql, qr, 0, 0, n);
}
private:
void recompute(int pos) {
tree[pos] = combine(tree[pos*2+1], tree[pos*2+2]);
}
void build(string&v, int pos, int l, int r) {
if (l >= v.size()) return;
if (l+1 == r) { tree[pos]=Value::Single(v[l]); return; }
int m = (l+r) / 2;
build(v, pos*2+1, l, m);
build(v, pos*2+2, m, r);
recompute(pos);
}
Value query(int ql, int qr, int pos, int l, int r) {
if (ql >= r || qr <= l) return Value::Identity();
if (ql <= l && qr >= r) return tree[pos];
int m = (l+r) / 2;
return combine(
query(ql, qr, pos*2+1, l, m),
query(ql, qr, pos*2+2, m, r)
);
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
string votes; cin >> votes;
Segtree seg(votes);
int q; cin >> q;
for (int i=0; i<q; i++) {
int l, r;
cin >> l >> r;
Value res = seg.query(l-1, r);
cout << max(res.inc, res.dec) << "\n";
}
}
Compilation message
election.cpp: In member function 'void Segtree::build(std::string&, long long int, long long int, long long int)':
election.cpp:52:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (l >= v.size()) return;
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
