#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int sf[N], p[N], n;
pii tree[4 * N][2];
void build(int u, int l,int r) {
if(l == r) {
int i = l;
tree[u][0] = {p[l], l}; tree[u][1] = {sf[i], -i};
return;
}
int mid = (l + r) /2 ;
build(2 * u, l, mid); build(2 * u + 1, mid + 1,r);
for(int t = 0; t < 2; t++) tree[u][t] = min(tree[2 * u][t], tree[2 * u + 1][t]);
}
pair<int,int> get(int u,int st,int en, int l,int r, int t) {
if(l > en || r < st) return {N, 0};
if(st <= l && r <= en) return tree[u][t];
int mid = (l + r) / 2;
return min(get(2 * u, st, en, l, mid, t), get(2 * u + 1, st,en, mid + 1, r, t));
}
pair<int,int> get(int l, int r, int t) {
pii x = get(1, l, r, 1, n, t);
if(t) x.f -= sf[r + 1]; else x.f -= p[l - 1];
if(t) x.s *= -1;
if(x.f >= 0) {
if(t) x = {0, r + 1};
else x = {0, l - 1};
} else x.f *= -1;
return x;
}
main() {
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// int p = 0;
cin >> n;
string s;
cin >> s;
s = '#' + s;
for(int i = 1; i <= n; i++) {
p[i] = p[i - 1];
p[i] += (s[i] == 'C' ? 1 : -1);
}
for(int i = n; i >= 1; i--) {
sf[i] = sf[i + 1];
sf[i] += (s[i] == 'C' ? 1 : -1);
}
build(1, 1, n);
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
pii x = get(l, r, 0), y = get(l, r, 1);
if(x.s < y.s) cout << x.f + y.f << endl;
else {
int b = min(x.f - get(l, y.s - 1, 0).f, y.f - get(x.s + 1, r, 1).f);
cout << x.f + y.f - b << endl;
}
}
}
Compilation message
election.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
37 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
