# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
521253 | MohamedFaresNebili | Election (BOI18_election) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
using db = double;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
struct node{
int pref, suff, sum, ans;
node operator+(node b) {
node res;
res.pref = max(pref, sum + b.pref);
res.suff = max(b.suff, a.suff + sum);
res.sum = sum + b.sum;
res.ans = max({pref + b.suff, ans + b.sum, b.ans + sum});
return res;
}
};
node st[4 * 500005];
string s; int n, q;
void build(int v, int l, int r) {
if(l == r) {
if(s[l] == 'T') st[v] = {1, 1, 1, 1};
else st[v] = {0, 0, -1, 0};
return;
}
build(v * 2, l, (l + r) / 2);
build(v * 2 + 1, (l + r) / 2 + 1, r);
st[v] = st[v * 2] + st[v * 2 + 1];
}
node query(int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return {0, 0, 0, 0};
if(l >= lo && r <= hi) return st[v];
return query(v * 2, l, (l + r) / 2, lo, hi) + query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s >> q;
build(1, 0, n - 1);
while(q--) {
int l, r; cin >> l >> r; l--; r--;
cout << query(1, 0, n - 1, l, r).ans << "\n";
}
}