#include <bits/stdc++.h>
#include <cmath>
using namespace std;
template<class T> struct Seg { // comb(ID,b) = b
const T ID = 1e18; T comb(T a, T b) { return min(a,b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // min on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
Seg<int> p;
Seg<int> s;
int main() {
int n; cin >> n;
int pref[n+1];
int suff[n+1];
int v[n];
p.init(n+1);
s.init(n+2);
pref[0] = 0;
suff[n+1] = 0;
char a;
for(int i = 1; i <= n; i++) {
cin >> a;
if (a == 'C') v[i] = 1;
else v[i] = -1;
pref[i] = pref[i-1] + v[i];
p.upd(i,pref[i]);
}
for(int i = n; i > 0; i--) {
suff[i] = suff[i+1] + v[i];
s.upd(i,suff[i]);
}
int q; cin >> q;
int b,c;
while (q--) {
cin >> b >> c;
cout << -min(p.query(b,c)-pref[b-1],s.query(b,c)-suff[c+1]) << endl;
}
}
Compilation message
election.cpp: In instantiation of 'Seg<int>::Seg()':
election.cpp:25:10: required from here
election.cpp:9:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
9 | const T ID = 1e18; T comb(T a, T b) { return min(a,b); }
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
