#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define It it=se.begin();it!=se.end();it++
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define all(x) begin(x),end(x)
#define unmap unordered_map
#define pii pair<int,int>
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vi vector<int>
#define ld long double
#define ll long long
#define pb push_back
#define sh short int
#define mid (l+r)/2
#define S second
#define F first
#define sqr 708
using namespace std;
const int inf = 1e9+9;
const ll mod = 1e9+7;
const int shift = 1e5;
const ld pai=acos(-1);
int n,q;
int a[500009][9];
int tree[2000009][9];
string s;
void build(int node,int l,int r,int id){
if(l == r) return void(tree[node][id]=a[l][id]);
build(node*2,l,mid,id),build(node*2+1,mid+1,r,id);
tree[node][id] = max(tree[node*2][id],tree[node*2+1][id]);
}
int query(int node,int l,int r,int s,int e,int id){
if(s <= l && e >= r) return tree[node][id];
if(s <= mid && e > mid){
int x = query(node*2,l,mid,s,e,id);
int y = query(node*2+1,mid+1,r,s,e,id);
return max(x,y);
}
if(s <= mid) return query(node*2,l,mid,s,e,id);
return query(node*2+1,mid+1,r,s,e,id);
}
int main(){
fast,cin>>n>>s;
s = '.' + s;
for(int i=1;i<=n;i++){
a[i][0] = a[i-1][0];
a[i][0] += (s[i] == 'T');
a[i][0] -= (s[i] == 'C');
}
for(int i=n;i>=1;i--){
a[i][1] = a[i+1][1];
a[i][1] += (s[i] == 'T');
a[i][1] -= (s[i] == 'C');
}
build(1,0,n,0);
build(1,0,n,1);
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
int x = query(1,0,n,l,r,0);
int y = query(1,0,n,l,r,1);
x -= a[l-1][0],y -= a[r+1][1];
cout<<max(0,max(x,y))<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
