//
// Created by 42kangaroo on 01/10/2022.
//
#include "bits/stdc++.h"
using namespace std;
#define int long long
struct Val {
int CSum, l, r, nul;
};
Val combine(const Val& l, const Val& r) {
Val res{l.CSum + r.CSum, l.l + max((int)0,r.l - max((int)0, (l.CSum - l.nul))),r.r +max((int)0, l.r - max((int)0,(r.CSum - r.nul))), 0};
res.nul = max(res.l, res.r);
return res;
}
pair<vector<bool>, int> input(){
int n, q;
cin >> n;
vector<bool> fans(n);
for (auto&& f: fans) {
char c;
cin >> c;
f = c == 'C';
}
cin >> q;
return {fans, q};
}
struct SegTe {
vector<Val> cache_;
Val build(int l, int r, int i, const vector<bool>& inputVec) {
if (l+1 >= r) return cache_[i] = (inputVec[l] ? Val{1, 0 ,0, 0} : Val{0, 1, 1, 1} );
int m = (l + r) / 2;
return cache_[i] = combine(build(l , m, 2*i+1, inputVec), build(m,r, 2*i+2, inputVec));
}
Val get(int l, int r, int i, int ql, int qr) {
if (qr <= l || ql >= r) return {0,0,0, 0};
if (ql <= l && qr >= r) return cache_[i];
int m = (l+r)/2;
return combine(get(l,m, 2*i+1, ql, qr), get(m,r,2*i+2, ql, qr));
}
SegTe(const vector<bool>& inputVec): cache_(inputVec.size()*4){
build(0, inputVec.size(), 0, inputVec);
}
};
signed main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
auto [fans, q] = input();
SegTe tree{fans};
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
cout << tree.get(0 ,fans.size(), 0 ,l-1, r).nul << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
