#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[r] + pref[l-1]);
sum_in = max(sum_in, max(0, -query(1, 1, N, l, r).mn_suff));
cout << sum_in + sum_out << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
131908 KB |
Output is correct |
2 |
Correct |
15 ms |
131900 KB |
Output is correct |
3 |
Correct |
16 ms |
131944 KB |
Output is correct |
4 |
Correct |
15 ms |
131932 KB |
Output is correct |
5 |
Correct |
16 ms |
131932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
131908 KB |
Output is correct |
2 |
Correct |
15 ms |
131900 KB |
Output is correct |
3 |
Correct |
16 ms |
131944 KB |
Output is correct |
4 |
Correct |
15 ms |
131932 KB |
Output is correct |
5 |
Correct |
16 ms |
131932 KB |
Output is correct |
6 |
Correct |
65 ms |
133712 KB |
Output is correct |
7 |
Correct |
66 ms |
133636 KB |
Output is correct |
8 |
Correct |
64 ms |
133768 KB |
Output is correct |
9 |
Correct |
64 ms |
133752 KB |
Output is correct |
10 |
Correct |
76 ms |
134228 KB |
Output is correct |
11 |
Correct |
69 ms |
134692 KB |
Output is correct |
12 |
Correct |
80 ms |
134028 KB |
Output is correct |
13 |
Correct |
75 ms |
134992 KB |
Output is correct |
14 |
Correct |
73 ms |
134224 KB |
Output is correct |
15 |
Correct |
86 ms |
135056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
131908 KB |
Output is correct |
2 |
Correct |
15 ms |
131900 KB |
Output is correct |
3 |
Correct |
16 ms |
131944 KB |
Output is correct |
4 |
Correct |
15 ms |
131932 KB |
Output is correct |
5 |
Correct |
16 ms |
131932 KB |
Output is correct |
6 |
Correct |
65 ms |
133712 KB |
Output is correct |
7 |
Correct |
66 ms |
133636 KB |
Output is correct |
8 |
Correct |
64 ms |
133768 KB |
Output is correct |
9 |
Correct |
64 ms |
133752 KB |
Output is correct |
10 |
Correct |
76 ms |
134228 KB |
Output is correct |
11 |
Correct |
69 ms |
134692 KB |
Output is correct |
12 |
Correct |
80 ms |
134028 KB |
Output is correct |
13 |
Correct |
75 ms |
134992 KB |
Output is correct |
14 |
Correct |
73 ms |
134224 KB |
Output is correct |
15 |
Correct |
86 ms |
135056 KB |
Output is correct |
16 |
Correct |
594 ms |
147600 KB |
Output is correct |
17 |
Correct |
403 ms |
147096 KB |
Output is correct |
18 |
Correct |
459 ms |
147428 KB |
Output is correct |
19 |
Correct |
458 ms |
146936 KB |
Output is correct |
20 |
Correct |
681 ms |
151248 KB |
Output is correct |
21 |
Correct |
1041 ms |
153164 KB |
Output is correct |
22 |
Correct |
651 ms |
151812 KB |
Output is correct |
23 |
Correct |
769 ms |
155444 KB |
Output is correct |
24 |
Correct |
705 ms |
154004 KB |
Output is correct |
25 |
Correct |
677 ms |
159716 KB |
Output is correct |