#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
int nxt[n]{}, lst = n, sz[n]{}, cnt = 0;
for (int i = n - 1; i >= 0; i--) {
nxt[i] = lst;
cnt += s[i] == 'T';
if (i - 1 >= 0 && s[i - 1] != s[i]) {
lst = i;
}
if (i - 1 < 0 || s[i - 1] == 'C') {
sz[i] = cnt;
cnt = 0;
}
}
int prv[n]{}, prf[n + 1]{};
lst = -1;
for (int i = 0; i < n; i++) {
prv[i] = lst;
if (i + 1 < n && s[i + 1] != s[i]) {
lst = i;
}
prf[i + 1] = prf[i] + (s[i] == 'C');
}
auto sum = [&] (int l, int r) {
return prf[r + 1] - prf[l];
};
int q;
cin >> q;
int ans[q]{};
for (int k = 0; k < q; k++) {
int l, r;
cin >> l >> r;
l--, r--;
if (s[l] == 'T') {
if (nxt[l] > r) {
ans[k] = r - l + 1;
continue;
}
ans[k] += nxt[l] - l;
l = nxt[l];
}
if (s[r] == 'T') {
ans[k] += r - prv[r];
r = prv[r];
}
for (int i = l; i <= r; i++) {
ans[k] += max(0, sz[i] - min(sum(l, i), sum(i, r)));
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
