#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#define cin fin
#define cout fout
const string FILE_NAME = "elections"; ifstream fin(FILE_NAME + ".in"); ofstream fout(FILE_NAME + ".out");
#endif
typedef long long ll;
// typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
// typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
// #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
// #define F0rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first
#define s second
#define pb push_back
// #define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;
struct info{
int t, c, t2, c2;
};
ostream& operator<< (ostream& stream, info x){
stream << x.t << " " << x.c << " " << x.t2 << " " << x.c2;
return stream;
}
struct SegTree{
int size;
vector<info> t;
SegTree(int _size){
if(__builtin_popcount(_size) != 1){
_size = 1 << (32 - __builtin_clz(_size));
}
size = _size;
t.resize(2 * size);
}
info merge(info a, info b){
info tmp = {0, 0, 0, 0};
tmp.c = b.c + max(0, a.c - b.t);
tmp.t = a.t + max(0, b.t - a.c);
tmp.c2 = a.c2 + max(0, b.c2 - a.t2);
tmp.t2 = b.t2 + max(0, a.t2 - b.c2);
return tmp;
}
info query(int x, int l, int r, int ql, int qr){
if(l > qr || r < ql){
return {0, 0, 0, 0};
}
if(l >= ql && r <= qr){
return t[x];
}
int m = (l + r) / 2;
return merge(query(2 * x, l, m, ql, qr), query(2 * x + 1, m + 1, r, ql, qr));
}
info query(int l, int r){
return query(1, 0, size - 1, l, r);
}
};
void solve(){
int n;
cin >> n;
SegTree tree(n);
for(int i = 0; i < n; ++i){
char c;
cin >> c;
if(c == 'C'){
tree.t[tree.size + i].c = 1;
tree.t[tree.size + i].c2 = 1;
}
else{
tree.t[tree.size + i].t = 1;
tree.t[tree.size + i].t2 = 1;
}
}
for(int i = tree.size - 1; i > 0; --i){
tree.t[i] = tree.merge(tree.t[2 * i], tree.t[2 * i + 1]);
}
/* for(int i = 1; i < 2 * tree.size; ++i){ */
/* cout << i << " " << tree.t[i] << nl; */
/* } */
int q; cin >> q;
for(int i = 0; i < q; ++i){
int l, r;
cin >> l >> r; --l, --r;
info tmp = tree.query(l, r);
cout << max(tmp.t, tmp.t2) << nl;
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int TC = 1;
// cin >> TC;
while(TC--){
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
