#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
const int M = 19;
int solve(vector<int> a, int i, int cnt, int bal, vector<int> res) {
if (i == a.size()) {
int rev_bal = 0;
for (int i = res.size() - 1; i; i--) {
rev_bal += res[i];
if (rev_bal < 0)
return 1e9;
}
return cnt;
}
int ans = 1e9;
if (a[i] == 1) {
res.push_back(1);
ans = min(ans, solve(a, i + 1, cnt, bal + 1, res));
} else {
ans = min(ans, solve(a, i + 1, cnt + 1, bal, res));
if (bal > 0) {
res.push_back(-1);
ans = min(ans, solve(a, i + 1, cnt, bal - 1, res));
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int n = 50;
cin >> n;
string s; //"TTCTCC";
// for (int i = 0; i < n; i++) {
// s += rand() % 2 ? 'C' : 'T';
// }
cin >> s;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
char c = s[i - 1];
a[i] = 1 - 2 * (c == 'T');
}
vector<int> pre(n + 1), suf(n + 2);
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i];
}
for (int i = n; i; i--) {
suf[i] = suf[i + 1] + a[i];
}
vector<int> pos(2 * n + 5, n + 1);
vector<vector<int>> nxt(n + 2, vector<int>(M, n + 1));
for (int i = n; i >= 0; i--) {
int tar = pre[i] - 1 - (a[i] == 1);
nxt[i][0] = pos[tar + n + 2];
pos[pre[i] + n + 2] = i;
}
for (int j = 1; j < M; j++) {
for (int i = 0; i <= n; i++) {
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
}
}
pos.assign(2 * n + 5, 0);
vector<vector<int>> prev(n + 2, vector<int>(M));
for (int i = 1; i <= n + 1; i++) {
int tar = suf[i] - 1 - (a[i] == 1);
prev[i][0] = pos[tar + n + 2];
pos[suf[i] + n + 2] = i;
}
for (int j = 1; j < M; j++) {
for (int i = 1; i <= n + 1; i++) {
prev[i][j] = prev[prev[i][j - 1]][j - 1];
}
}
auto get_l_info = [&](int l, int r) -> array<int, 2> {
if (a[l] == 1)
l = nxt[l][0];
int cnt = 0;
for (int i = M - 1; i >= 0; i--) {
if (nxt[l][i] <= r) {
l = nxt[l][i];
cnt += 1 << i;
}
}
return {l, cnt + (l <= r)};
};
auto get_r_info = [&](int l, int r) -> array<int, 2> {
if (a[r] == 1)
r = prev[r][0];
int cnt = 0;
for (int i = M - 1; i >= 0; i--) {
if (prev[r][i] >= l) {
r = prev[r][i];
cnt += 1 << i;
}
}
return {r, cnt + (l <= r)};
};
int q = 1;
cin >> q;
while (q--) {
int l = 1, r = n;
cin >> l >> r;
auto l1 = get_l_info(l, r);
auto r1 = get_r_info(l, r);
if (l1[0] < r1[0]) {
cout << l1[1] + r1[1] << "\n";
continue;
}
auto l2 = get_l_info(l, min(l1[0], r1[0]) - 1);
auto r2 = get_r_info(max(l1[0], r1[0]) + 1, r);
int ans = l2[1] + r2[1];
ans += max(l1[1] - l2[1], r1[1] - r2[1]);
cout << ans << "\n";
// int ans2 = solve(a, 1, 0, 0, {});
// if (ans != ans2) {
// cout << s << "\n";
// cout << l1[0] << " " << l1[1] << " " << r1[0] << " " << r1[1] << "\n";
// cout << l2[0] << " " << l2[1] << " " << r2[0] << " " << r2[1] << "\n";
// cout << ans << " " << ans2 << "\n";
// }
}
}
Compilation message
election.cpp: In function 'int solve(std::vector<int>, int, int, int, std::vector<int>)':
election.cpp:10:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | if (i == a.size()) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
