Submission #855019

#TimeUsernameProblemLanguageResultExecution timeMemory
855019ivazivaElection (BOI18_election)C++14
0 / 100
4 ms6492 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...