This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500010
long long n;
long long q;
string s;
long long pref1[MAXN];
long long pref2[MAXN];
long long seg1[MAXN*4];
long long seg2[MAXN*4];
void build1(long long node,long long l,long long r)
{
if (l==r) seg1[node]=pref1[l];
else
{
long long mid=(l+r)/2;
build1(2*node,l,mid);
build1(2*node+1,mid+1,r);
seg1[node]=min(seg1[2*node],seg1[2*node+1]);
}
}
void build2(long long node,long long l,long long r)
{
if (l==r) seg2[node]=pref2[l];
else
{
long long mid=(l+r)/2;
build2(2*node,l,mid);
build2(2*node+1,mid+1,r);
seg2[node]=min(seg2[2*node],seg2[2*node+1]);
}
}
long long get1(long long node,long long l,long long r,long long a,long long b)
{
if (a>b) return LLONG_MAX;
else if (l==a and r==b) return seg1[node];
long long mid=(l+r)/2;
return min(get1(2*node,l,mid,a,min(b,mid)),get1(2*node+1,mid+1,r,max(a,mid+1),b));
}
long long get2(long long node,long long l,long long r,long long a,long long b)
{
if (a>b) return LLONG_MAX;
else if (l==a and r==b) return seg2[node];
long long mid=(l+r)/2;
return min(get2(2*node,l,mid,a,min(b,mid)),get2(2*node+1,mid+1,r,max(a,mid+1),b));
}
int main()
{
ios_base::sync_with_stdio(false);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
pref1[0]=0;
for (long long i=1;i<=n;i++)
{
if (s[i-1]=='C') pref1[i]=pref1[i-1]+1;
else pref1[i]-pref1[i-1]-1;
}
pref2[n+1]=0;
for (long long i=n;i>=1;i--)
{
if (s[i-1]=='C') pref2[i]=pref2[i+1]+1;
else pref2[i]=pref2[i+1]-1;
}
build1(1,1,n);
build2(1,1,n);
cin>>q;
for (long long i=1;i<=q;i++)
{
long long l,r;
cin>>l>>r;
long long d1=get1(1,1,n,l,r)-pref1[l-1];
long long d2=get2(1,1,n,l,r)-pref2[r+1];
if (d1>=0 and d2>=0) cout<<0<<endl;
else if (d1>=0 and d2<0) cout<<abs(d2)<<endl;
else if (d1<0 and d2>=0) cout<<abs(d1)<<endl;
else cout<<max(abs(d1),abs(d2))<<endl;
}
}
Compilation message (stderr)
election.cpp: In function 'int main()':
election.cpp:66:33: warning: statement has no effect [-Wunused-value]
66 | else pref1[i]-pref1[i-1]-1;
| ~~~~~~~~~~~~~~~~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |