Submission #519847

#TimeUsernameProblemLanguageResultExecution timeMemory
519847ahmedfouadnewElection (BOI18_election)C++17
0 / 100
4 ms332 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define f first #define s second int sum[500005][2],n,q; int mni[4*500005][2]; string s; int build(int ni,int ns,int ne,bool d) { if(ns==ne) { return mni[ni][d]=ns; } int mid=ns+(ne-ns)/2; int x=build(ni*2+1,ns,mid,d); int y=build(ni*2+2,mid+1,ne,d); if(sum[x][d]>=sum[y][d]) mni[ni][d]=x; else mni[ni][d]=y; return mni[ni][d]; } int query(int ni,int ns,int ne,int nl,int nr,bool d) { if(nr<ns||ne<nl) return n; if(nl<=ns&&ne<=nr) return mni[ni][d]; int mid=ns+(ne-ns)/2; int x=query(ni*2+1,ns,mid,nl,nr,d); int y=query(ni*2+2,mid+1,ne,nl,nr,d); if(sum[x][d]>=sum[y][d]) return x; return y; } signed main() { ios_base::sync_with_stdio(0); cin>>n; cin>>s; for(int i=0;i<n;i++) { if(!i) { sum[i][0]=2*(s[i]=='T')-1; } else sum[i][0]=2*(s[i]=='T')-1+sum[i-1][0]; } for(int i=n-1;i>=0;i--) { if(i==n-1) { sum[i][1]=2*(s[i]=='T')-1; } else sum[i][1]=2*(s[i]=='T')-1+sum[i+1][1]; } sum[n][0]=sum[n][1]=-1e9; build(0,0,n-1,0); build(0,0,n-1,1); cin>>q; int l,r; while(q--) { cin>>l>>r; l--,r--; int pr=query(0,0,n-1,l,r,0),sf=query(0,0,n-1,l,r,1); int ans=max(sum[pr][0]-(l?sum[l-1][0]:0),sum[sf][1]-(r==n-1?0:sum[r+1][1])); ans=max(ans,0ll); cout<<ans<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...