#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
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) {
int k = lg2[r - l + 1];
return max(rmq[t][k][l], rmq[t][k][r - (1 << k) + 1]);
}
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], 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> tmp = get(1, l, r);
int res = max(0, tmp.first + fc[1][r + 1] - ft[1][r + 1]);
if (l < tmp.second) {
res += max(0, get(0, l, tmp.second - 1).first + fc[0][l - 1] - ft[0][l - 1]);
}
cout << res << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
