#include <bits/stdc++.h>
using namespace std;
struct Node { int sum, L, R, ans; } tree[2000010];
int N, Q; char S[500010];
Node comb(Node A, Node B) {
Node res; res.sum = A.sum + B.sum; res.L = max(A.L, A.sum + B.L); res.R = max(B.R, A.R + B.sum);
res.ans = max(max(A.ans + B.sum, A.sum + B.ans), A.L + B.R); return res;
}
void build(int x, int l, int r) { int mid = (l + r) / 2;
if (l == r) { if (S[l] == 'T') tree[x] = {1, 1, 1, 1}; else tree[x] = {-1, 0, 0, 0}; return ; }
build(2 * x, l, mid); build(2 * x + 1, mid + 1, r); tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}
Node query(int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
if (r < tl || l > tr) return Node {0, 0, 0, 0}; if (tl <= l && r <= tr) return tree[x];
return comb(query(2 * x, l, mid, tl, tr), query(2 * x + 1, mid + 1, r, tl, tr));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N; for (int i = 1; i <= N; i++) cin >> S[i]; build(1, 1, N);
cin >> Q; for (int i = 0; i < Q; i++) { int A, B; cin >> A >> B;
cout << query(1, 1, N, A, B).ans << endl;
}
}
Compilation message
election.cpp: In function 'Node query(int, int, int, int, int)':
election.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
20 | if (r < tl || l > tr) return Node {0, 0, 0, 0}; if (tl <= l && r <= tr) return tree[x];
| ^~
election.cpp:20:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
20 | if (r < tl || l > tr) return Node {0, 0, 0, 0}; if (tl <= l && r <= tr) return tree[x];
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
364 KB |
Output is correct |
3 |
Correct |
6 ms |
364 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
364 KB |
Output is correct |
3 |
Correct |
6 ms |
364 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
364 KB |
Output is correct |
6 |
Correct |
228 ms |
4716 KB |
Output is correct |
7 |
Correct |
215 ms |
5740 KB |
Output is correct |
8 |
Correct |
216 ms |
5740 KB |
Output is correct |
9 |
Correct |
207 ms |
5868 KB |
Output is correct |
10 |
Correct |
221 ms |
5740 KB |
Output is correct |
11 |
Correct |
223 ms |
5868 KB |
Output is correct |
12 |
Correct |
223 ms |
5868 KB |
Output is correct |
13 |
Correct |
216 ms |
5996 KB |
Output is correct |
14 |
Correct |
218 ms |
5868 KB |
Output is correct |
15 |
Correct |
226 ms |
5868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
364 KB |
Output is correct |
3 |
Correct |
6 ms |
364 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
364 KB |
Output is correct |
6 |
Correct |
228 ms |
4716 KB |
Output is correct |
7 |
Correct |
215 ms |
5740 KB |
Output is correct |
8 |
Correct |
216 ms |
5740 KB |
Output is correct |
9 |
Correct |
207 ms |
5868 KB |
Output is correct |
10 |
Correct |
221 ms |
5740 KB |
Output is correct |
11 |
Correct |
223 ms |
5868 KB |
Output is correct |
12 |
Correct |
223 ms |
5868 KB |
Output is correct |
13 |
Correct |
216 ms |
5996 KB |
Output is correct |
14 |
Correct |
218 ms |
5868 KB |
Output is correct |
15 |
Correct |
226 ms |
5868 KB |
Output is correct |
16 |
Correct |
1750 ms |
27116 KB |
Output is correct |
17 |
Correct |
1657 ms |
26680 KB |
Output is correct |
18 |
Correct |
1674 ms |
26860 KB |
Output is correct |
19 |
Correct |
1580 ms |
26532 KB |
Output is correct |
20 |
Correct |
1759 ms |
26268 KB |
Output is correct |
21 |
Correct |
1744 ms |
28012 KB |
Output is correct |
22 |
Correct |
1754 ms |
27848 KB |
Output is correct |
23 |
Correct |
1762 ms |
27932 KB |
Output is correct |
24 |
Correct |
1751 ms |
27812 KB |
Output is correct |
25 |
Correct |
1733 ms |
27156 KB |
Output is correct |