#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*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] = {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 |
600 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
