#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 5*1e5+5, INF = 4e18+9;
ll n, Q;
string s;
void inp(){
cin >> n;
cin >> s;
s = ' ' + s;
cin >> Q;
}
struct Node{
ll L, R, S, res;
};
ll N;
Node T[4*maxn];
Node merg(Node a, Node b){
Node res;
res.S = a.S+b.S;
res.L = max(a.L, a.S+b.L);
res.R = max(b.R, a.R+b.S);
res.res = max(max(a.S+b.res, a.res+b.S), a.L+b.R);
return res;
}
void build_segtree(){
N = 1;
while(N < n) N*=2;
for(int i = 1; i <= n; i++){
if(s[i] == 'C'){
T[i+N-1] = {0, 0, -1, 0};
}else{
T[i+N-1] = {1, 1, 1, 1};
}
}
for(int i = n+1; i <= N; i++){
T[i+N-1] = {0, 0, 0, 0};
}
for(int i = N-1; i >= 1; i--){
T[i] = merg(T[i*2], T[i*2+1]);
}
}
Node get(int node, int low, int high, int l, int r){
if(low > r || l > high) return {0, 0, 0, 0};
if(low >= l && r >= high) return T[node];
int mid = (low+high)/2;
return merg(get(node*2, low, mid, l, r), get(node*2+1, mid+1, high, l, r));
}
void solve(){
build_segtree();
int l, r;
for(int i = 1; i <= Q; i++){
cin >> l >> r;
cout << get(1, 1, N, l, r).res << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
inp();
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
56 ms |
9108 KB |
Output is correct |
7 |
Correct |
47 ms |
9300 KB |
Output is correct |
8 |
Correct |
47 ms |
9044 KB |
Output is correct |
9 |
Correct |
40 ms |
9192 KB |
Output is correct |
10 |
Correct |
50 ms |
9044 KB |
Output is correct |
11 |
Correct |
47 ms |
9292 KB |
Output is correct |
12 |
Correct |
46 ms |
9224 KB |
Output is correct |
13 |
Correct |
47 ms |
9296 KB |
Output is correct |
14 |
Correct |
48 ms |
9168 KB |
Output is correct |
15 |
Correct |
47 ms |
9048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
600 KB |
Output is correct |
6 |
Correct |
56 ms |
9108 KB |
Output is correct |
7 |
Correct |
47 ms |
9300 KB |
Output is correct |
8 |
Correct |
47 ms |
9044 KB |
Output is correct |
9 |
Correct |
40 ms |
9192 KB |
Output is correct |
10 |
Correct |
50 ms |
9044 KB |
Output is correct |
11 |
Correct |
47 ms |
9292 KB |
Output is correct |
12 |
Correct |
46 ms |
9224 KB |
Output is correct |
13 |
Correct |
47 ms |
9296 KB |
Output is correct |
14 |
Correct |
48 ms |
9168 KB |
Output is correct |
15 |
Correct |
47 ms |
9048 KB |
Output is correct |
16 |
Correct |
494 ms |
42872 KB |
Output is correct |
17 |
Correct |
391 ms |
43396 KB |
Output is correct |
18 |
Correct |
452 ms |
43384 KB |
Output is correct |
19 |
Correct |
371 ms |
43048 KB |
Output is correct |
20 |
Correct |
495 ms |
42852 KB |
Output is correct |
21 |
Correct |
456 ms |
44536 KB |
Output is correct |
22 |
Correct |
483 ms |
44240 KB |
Output is correct |
23 |
Correct |
495 ms |
44620 KB |
Output is correct |
24 |
Correct |
491 ms |
44120 KB |
Output is correct |
25 |
Correct |
499 ms |
43768 KB |
Output is correct |