// Author: caption_mingle
#include "bits/stdc++.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 5e5 + 7;
int n, q;
int a[N];
struct Node {
int lef, rig, tot, ans;
Node() {
lef = rig = tot = ans = 0;
}
Node(int x) {
tot = x;
lef = rig = ans = max(0, x);
}
Node operator + (const Node& o) {
Node tmp;
tmp.lef = max(lef, tot + o.lef);
tmp.rig = max(o.rig, rig + o.tot);
tmp.tot = tot + o.tot;
tmp.ans = max({lef + o.rig, ans + o.tot, tot + o.ans});
return tmp;
}
} st[N * 4 + 4];
void build(int i = 1, int l = 1, int r = n) {
if(l == r) {
st[i] = Node(a[l]);
return;
}
int m = (l + r) >> 1;
build(i * 2, l, m);
build(i * 2 + 1, m + 1, r);
st[i] = st[i * 2] + st[i * 2 + 1];
}
Node get(int i, int l, int r, int u, int v) {
if(l > v or r < u) return Node();
if(u <= l and r <= v) return st[i];
int m = (l + r) >> 1;
return get(i * 2, l, m, u, v) + get(i * 2 + 1, m + 1, r, u, v);
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#define task ""
if(fopen(task ".INP", "r")) {
freopen(task ".INP", "r", stdin);
freopen(task ".OUT", "w", stdout);
}
cin >> n;
for(int i = 1; i <= n; i++) {
char c; cin >> c;
if(c == 'T') a[i] = 1;
else a[i] = -1;
}
cin >> q;
build();
for(int i = 1; i <= q; i++) {
int l, r; cin >> l >> r;
cout << get(1, 1, n, l, r).ans << ln;
}
cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}
Compilation message (stderr)
election.cpp: In function 'int main()':
election.cpp:60:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | freopen(task ".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | freopen(task ".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |