#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
const int INF = 1e9;
int n, m;
int lg2[N];
int fc[2][N], ft[2][N];
pair<int, int> rmq[2][20][N];
string s;
pair<int, int> get(int t, int l, int r) {
if (l > r) return {-INF, 0};
int k = lg2[r - l + 1];
return max(rmq[t][k][l], rmq[t][k][r - (1 << k) + 1]);
}
//ctctcct
int main() {
ios::sync_with_stdio(false);
cin >> n >> s, s = ' ' + s;
for (int i = 1; i <= n; ++i) {
fc[0][i] = fc[0][i - 1] + (s[i] == 'C');
ft[0][i] = ft[0][i - 1] + (s[i] == 'T');
}
for (int i = n; i >= 1; --i) {
fc[1][i] = fc[1][i + 1] + (s[i] == 'C');
ft[1][i] = ft[1][i + 1] + (s[i] == 'T');
}
for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
for (int t = 0; t < 2; ++t) {
for (int i = 1; i <= n; ++i) {
rmq[t][0][i] = {ft[t][i] - fc[t][i], (t == 0) ? -i : i};
}
for (int i = 1; i < 20; ++i) {
for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
rmq[t][i][j] = max(rmq[t][i - 1][j], rmq[t][i - 1][j + (1 << (i - 1))]);
}
}
}
cin >> m;
while (m--) {
int l, r; cin >> l >> r;
pair<int, int> tmp0 = get(0, l, r);
tmp0.first += -ft[0][l - 1] + fc[0][l - 1];
tmp0.second = -tmp0.second;
pair<int, int> tmp1 = get(1, l, r);
tmp1.first += -ft[1][r + 1] + fc[1][r + 1];
if (tmp0.first <= 0) tmp0.first = 0, tmp0.second = l - 1;
if (tmp1.first <= 0) tmp1.first = 0, tmp1.second = r + 1;
if (tmp0.first < tmp1.first) {
tmp0 = get(0, l, tmp1.second - 1);
tmp0.first += -ft[0][l - 1] + fc[0][l - 1];
tmp0.first = max(0, tmp0.first);
}
else {
tmp1 = get(1, tmp0.second + 1, r);
tmp1.first += -ft[1][r + 1] + fc[1][r + 1];
tmp1.first = max(0, tmp1.first);
}
cout << tmp0.first + tmp1.first << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
