#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 5e5 + 5;
int N, nxt[LOGN][MAXN], l, r, pref[MAXN];
int out[LOGN][MAXN], in[LOGN][MAXN];
map<int,int> occur;
vector<int> A;
string S;
struct Node {
int sum, mn_suff;
Node() : sum(0), mn_suff(0) { }
Node(int s, int m) : sum(s), mn_suff(m) { }
} tmp, sg[4*MAXN];
Node merge(Node a, Node b) {
Node new_node;
new_node.sum = a.sum + b.sum;
new_node.mn_suff = min(a.mn_suff + b.sum, b.mn_suff);
return new_node;
}
void init(int k, int a, int b) {
if (a == b) {
sg[k] = Node(A[a], A[a]);
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
Node query(int k, int a, int b, int q_l, int q_r) {
if (q_r < a || q_l > b)
return tmp;
if (q_l <= a && b <= q_r)
return sg[k];
return merge(query(2*k, a, (a+b)/2, q_l, q_r), query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}
int main() {
fast
cin >> N >> S;
A = vector<int>(N+1);
for (int i = 1; i <= N; i++) {
A[i] = (S[i-1] == 'C' ? 1 : -1);
pref[i] = pref[i-1] + A[i];
}
init(1, 1, N);
int now = 0;
nxt[0][N+1] = N+1;
for (int i = N; i >= 1; i--) {
now += A[i];
if (A[i] == -1) {
nxt[0][i] = i+1;
out[0][i] = 1;
} else if (occur[now]) {
nxt[0][i] = occur[now];
in[0][i] = max(0, -query(1, 1, N, i, nxt[0][i] - 1).mn_suff);
} else {
nxt[0][i] = N+1;
in[0][i] = max(0, -query(1, 1, N, i, nxt[0][i] - 1).mn_suff);
}
occur[now] = i;
}
for (int i = 1; i < LOGN; i++) {
for (int j = 1; j <= N+1; j++) {
nxt[i][j] = nxt[i-1][nxt[i-1][j]];
in[i][j] = max(in[i-1][j], in[i-1][nxt[i-1][j]]);
out[i][j] = out[i-1][j] + out[i-1][nxt[i-1][j]];
}
}
int Q;
cin >> Q;
while (Q--) {
cin >> l >> r;
int sum_in = 0, sum_out = 0;
for (int i = LOGN - 1; i >= 0; i--) {
if (nxt[i][l] <= r) {
sum_out += out[i][l];
sum_in = max(sum_in, in[i][l]);
l = nxt[i][l];
}
}
sum_in = max(0, sum_in - pref[N] + pref[l-1]);
sum_in = max(sum_in, max(0, -query(1, 1, N, l, r).mn_suff));
cout << sum_in + sum_out << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
131920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
131920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
131920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
