Submission #759404

#TimeUsernameProblemLanguageResultExecution timeMemory
759404BulaElection (BOI18_election)C++17
0 / 100
17 ms35592 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=1e9+7,N=5e5+1; vector<int> pref(N),suf(N+1),t(4*N),t1(4*N),t2(4*N),t3(4*N); int getans(int v,int tl,int tr,int l,int r){ if(l>r) return -INT_MAX; if(l==tl && r==tr){ return t[v]; } int tm=(tl+tr)/2; return max(getans(v*2,tl,tm,l,min(r,tm)),getans(v*2+1,tm+1,tr,max(l,tm+1),r)); } void build(int v,int tl,int tr){ if(tl==tr){ t[v]=pref[tl]; }else{ int tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); t[v]=max(t[v*2],t[v*2+1]); } } ///// int getans1(int v,int tl,int tr,int l,int r){ if(l>r) return -INT_MAX; if(l==tl && r==tr){ return t1[v]; } int tm=(tl+tr)/2; return max(getans1(v*2,tl,tm,l,min(r,tm)),getans1(v*2+1,tm+1,tr,max(l,tm+1),r)); } void build1(int v,int tl,int tr){ if(tl==tr){ t1[v]=suf[tl]; }else{ int tm=(tl+tr)/2; build1(v*2,tl,tm); build1(v*2+1,tm+1,tr); t1[v]=max(t1[v*2],t1[v*2+1]); } } //// int getans2(int v,int tl,int tr,int l,int r){ if(l>r) return INT_MAX; if(l==tl && r==tr){ return t2[v]; } int tm=(tl+tr)/2; return min(getans2(v*2,tl,tm,l,min(r,tm)),getans2(v*2+1,tm+1,tr,max(l,tm+1),r)); } void build2(int v,int tl,int tr){ if(tl==tr){ t2[v]=pref[tl]; }else{ int tm=(tl+tr)/2; build2(v*2,tl,tm); build2(v*2+1,tm+1,tr); t2[v]=min(t2[v*2],t2[v*2+1]); } } ///// int getans3(int v,int tl,int tr,int l,int r){ if(l>r) return INT_MAX; if(l==tl && r==tr){ return t3[v]; } int tm=(tl+tr)/2; return min(getans3(v*2,tl,tm,l,min(r,tm)),getans3(v*2+1,tm+1,tr,max(l,tm+1),r)); } void build3(int v,int tl,int tr){ if(tl==tr){ t3[v]=suf[tl]; }else{ int tm=(tl+tr)/2; build3(v*2,tl,tm); build3(v*2+1,tm+1,tr); t3[v]=min(t3[v*2],t3[v*2+1]); } } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n; cin>>n; string s; cin>>s; vector<int> v(n+1); for(int i=1;i<=n;i++){ if(s[i-1]=='T') v[i]=1; else v[i]=-1; } for(int i=1;i<=n;i++){ pref[i]=pref[i-1]+v[i]; } for(int i=n;i>=1;i--){ suf[i]=suf[i+1]+v[i]; } build(1,1,n); build1(1,1,n); build2(1,1,n); build3(1,1,n); //for(int i=1;i<=n;i++) cout<<pref[i]<<" "; //cout<<endl; //for(int i=1;i<=n;i++) cout<<suf[i]<<" "; //cout<<endl; int q; cin>>q; for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; int ans=0; ans=max(ans,getans(1,1,n,l,r)-pref[l-1]); ans=max(ans,getans1(1,1,n,l,r)-suf[r+1]); ans=max(ans,getans2(1,1,n,l,r)-pref[l-1]); ans=max(ans,getans3(1,1,n,l,r)-suf[r+1]); cout<<ans<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...