#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
#define pb(x) push_back(x);
#define pp() pop_back();
const int L = 5e5+10, inf = 1e9;
int n;
int vote[L],ps[L],ss[L];
random_device device;
default_random_engine rng(device());
#define randt(a,b) uniform_int_distribution<int64_t>(a,b)(rng)
void pr(int* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void prv(vector<int> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void prl(long long* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void prvl(vector<long long> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void prp(pii* vv,int l,int r){for(int i=l;i<r;i++){cout<<i<<": "<<vv[i].f<<" , "<<vv[i].s<<" / ";}cout<<endl;}
struct sagi{
struct node{
int mn;
node(){
mn = inf;
}
}t[L<<2];
void build(int id,int l,int r,int* a){
if(l+1 == r){
t[id].mn = a[l];
return;
}
int mid = (l+r)>>1;
build(2*id+0,l,mid,a);
build(2*id+1,mid,r,a);
t[id].mn = min(t[2*id+0].mn,t[2*id+1].mn);
}
int get(int id,int l,int r,int l2,int r2){
if(l==l2 and r==r2){
return t[id].mn;
}
int mid = (l2+r2)>>1;
int ans = inf;
if(l<mid)
ans = min(ans, get(2*id+0,l,min(r,mid),l2,mid));
if(r>mid)
ans = min(ans, get(2*id+1,max(l,mid),r,mid,r2));
return ans;
}
}pseg,sseg;
int main(){
//ofstream cout ("out.txt");
//ifstream cin ("in.txt");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
map<char,int> inpc;
inpc['C'] = 1;
inpc['T'] = -1;
for(int i=1;i<=n;i++){
char inp;
cin>>inp;
vote[i] = inpc[inp];
}
ps[0] = ss[n+1] = 0;
for(int i=1;i<=n;i++){
ps[i] = ps[i-1] + vote[i];
}
for(int i=n;i>=1;i--){
ss[i] = ss[i+1] + vote[i];
}
pseg.build(1,1,n+1,ps);
sseg.build(1,1,n+1,ss);
int q;
cin>>q;
for(int tt=0;tt<q;tt++){
int l,r;
cin>>l>>r;
int db = pseg.get(1,l,r+1,1,n+1) - ps[l-1];
int df = sseg.get(1,l,r+1,1,n+1) - ss[r+1];
db = min(db,df);
if(db >= 0){
cout<<0<<endl;
}
else{
cout<<-db<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
15964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
