Submission #1050410

#TimeUsernameProblemLanguageResultExecution timeMemory
1050410MrAndriaElection (BOI18_election)C++14
0 / 100
4 ms2396 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back //#define int long long int n,q; string s; int p[200005],suff[200005],l,r; pair <int,int> d[200005],d1[200005]; void buildmax(int v,int tl,int tr){ if(tl==tr){ d[v]=make_pair(suff[tl],tl); return; } int tm=(tl+tr)/2; buildmax(2*v,tl,tm); buildmax(2*v+1,tm+1,tr); d[v]=max(d[2*v],d[2*v+1]); } pair <int,int> segmax(int v,int tl,int tr,int l,int r){ if(l>r){ return make_pair(0,0); } if(tl==l and tr==r){ return d[v]; } int tm=(tl+tr)/2; return max(segmax(2*v,tl,tm,l,min(r,tm)),segmax(2*v+1,tm+1,tr,max(l,tm+1),r)); } void buildmin(int v,int tl,int tr){ if(tl==tr){ d1[v]=make_pair(p[tl],tl); return; } int tm=(tl+tr)/2; buildmin(2*v,tl,tm); buildmin(2*v+1,tm+1,tr); d1[v]=min(d1[2*v],d1[2*v+1]); } pair <int,int> segmin(int v,int tl,int tr,int l,int r){ if(l>r){ return make_pair(INT_MAX,INT_MAX); } if(tl==l and tr==r){ // cout<<d1[v].ss<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl; return d1[v]; } int tm=(tl+tr)/2; // cout<<tm<<endl; return min(segmin(2*v,tl,tm,l,min(r,tm)),segmin(2*v+1,tm+1,tr,max(l,tm+1),r)); } int main(){ cin>>n; cin>>s; s=" "+s; for(int i=1;i<=n;i++){ p[i]=p[i-1]; if(s[i]=='T'){ p[i]--; }else{ p[i]++; } } for(int i=n;i>=1;i--){ suff[i]=suff[i+1]; if(s[i]=='T'){ suff[i]++; }else{ suff[i]--; } } buildmax(1,1,n); buildmin(1,1,n); cin>>q; // cout<<segmin(1,1,n,3,4).ss<<endl; while(q--){ cin>>l>>r; auto pos1=segmin(1,1,n,l,r); auto pos2=segmax(1,1,n,l,r); // cout<<pos1.ss<<" "<<pos2.ss<<endl; if(pos1.ss<pos2.ss){ cout<<abs(pos1.ff-p[l-1])+abs(-(pos2.ff-suff[r+1]))<<endl; continue; } auto k=segmin(1,1,n,l,pos2.ss-1); // cout<<k.ff<<" "<<k.ss<<endl; int fir=abs(min(0,k.ff-p[l-1])); if(k.ss==0){ fir=0; } k=segmax(1,1,n,pos1.ss+1,r); // cout<<k.ff<<" "<<k.ss<<endl; int sec=abs(min(0,-(k.ff-suff[r+1]))); if(k.ss==0){ sec=0; } // cout<<fir<<" "<<sec<<endl; cout<<fir+sec+max(abs(min(0,pos1.ff-p[l-1]))-fir,abs(min(0,-(pos2.ff-suff[r+1])))-sec)<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...