/**
We have empty array and queries:
0: add x in the end of array
1: on segment l..r for number x find such a[i] that (a[i] xor x) is maximal
2: delete last k elements from array
3: on segment l..r for number x find amount of numbers >=x
4: on segment l..r find k-th element (if sorted)
1 <= M <= 500000
1 <= x <= 500000
1 <= L <= R <= n
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
const int N = 5e5 + 11;
const int MAX=524287;
int v[N*60],l1[N*60],r1[N*60],kol;
int root[N];
void update(int deep, int i1, int i2, int l, int r, int x)
{
if (l==r) {v[i1]=v[i2]+1; return;}
int mid=(l+r)>>1;
if ((x&(1<<deep))==0)
{
kol++;
l1[i1]=kol;
r1[i1]=r1[i2];
update(deep-1,l1[i1],l1[i2],l,mid,x);
} else
{
kol++;
r1[i1]=kol;
l1[i1]=l1[i2];
update(deep-1,r1[i1],r1[i2],mid+1,r,x);
}
v[i1]=v[l1[i1]]+v[r1[i1]];
}
void build(int i, int l, int r)
{
v[i]=0;
if (l==r) return;
int mid=(l+r)>>1;
kol++;
l1[i]=kol;
kol++;
r1[i]=kol;
build(l1[i],l,mid);
build(r1[i],mid+1,r);
}
int get1(int deep, int i1, int i2, int l, int r, int x)
{
if (l==r) return l;
int mid=(l+r)>>1;
//cout<<l<<" "<<r<<" "<<x<<endl;
if ((x&(1<<deep))==0)
{
//cout<<"0 - "<<v[r1[i2]]-v[r1[i1]]<<endl;
if (v[r1[i2]]-v[r1[i1]]>0) return get1(deep-1,r1[i1],r1[i2],mid+1,r,x);
return get1(deep-1,l1[i1],l1[i2],l,mid,x);
} else
{
//cout<<"1 - "<<v[l1[i2]]-v[l1[i1]]<<endl;
if (v[l1[i2]]-v[l1[i1]]>0) return get1(deep-1,l1[i1],l1[i2],l,mid,x);
return get1(deep-1,r1[i1],r1[i2],mid+1,r,x);
}
}
int get3(int deep, int i1, int i2, int l, int r, int x)
{
if (l==r) return v[i2]-v[i1];
int mid=(l+r)>>1;
if (x<=mid) return get3(deep-1,l1[i1],l1[i2],l,mid,x);
else return v[l1[i2]]-v[l1[i1]]+get3(deep-1,r1[i1],r1[i2],mid+1,r,x);
}
int get4(int i1, int i2, int l, int r, int x)
{
if (l==r) return l;
int mid=(l+r)>>1;
int k=v[l1[i2]]-v[l1[i1]];
if (k>=x) return get4(l1[i1],l1[i2],l,mid,x);
else return get4(r1[i1],r1[i2],mid+1,r,x-k);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m;
cin>>n;
string s;
cin>>s>>m;
for(int i=0; i<m; ++i)
{
int l,r;
cin>>l>>r;
--l,--r;
int c(0),c1(0),cnt(0),f(0),cnt1(0);
for(int j=l; j<=r; ++j)
{
cnt+=(s[j]=='C');
cnt1+=(s[j]=='T');
if(cnt<cnt1-f)
{
++f;
++c;
}
}
cnt=0,f=0,cnt1=0;
for(int j=r; j>=l; --j)
{
cnt+=(s[j]=='C');
cnt1+=(s[j]=='T');
if(cnt<cnt1-f)
{
++f;
++c1;
}
}
cout<<max(c,c1)<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
