제출 #1178203

#제출 시각아이디문제언어결과실행 시간메모리
1178203AlgorithmWarriorElection (BOI18_election)C++20
100 / 100
839 ms19760 KiB
#include <bits/stdc++.h> using namespace std; int const MAX=500005; struct node{ int rez,ult,maxim,minim; }; struct AINT{ int n; node v[4*MAX]; node combine(node a,node b){ return { .rez=max(max(a.rez,b.rez),b.maxim+a.ult-a.minim), .ult=a.ult+b.ult, .maxim=max(a.maxim,b.maxim+a.ult), .minim=min(a.minim,b.minim+a.ult) }; } void update(int nod,int st,int dr,int poz,int val){ if(st==dr) v[nod]={0,val,val,val}; else{ int mij=(st+dr)/2; if(poz<=mij) update(2*nod,st,mij,poz,val); else update(2*nod+1,mij+1,dr,poz,val); v[nod]=combine(v[2*nod],v[2*nod+1]); } } node query(int nod,int st,int dr,int a,int b){ if(a<=st && dr<=b) return v[nod]; node ans={0,0,0,0}; int mij=(st+dr)/2; if(a<=mij) ans=combine(ans,query(2*nod,st,mij,a,b)); if(b>mij) ans=combine(ans,query(2*nod+1,mij+1,dr,a,b)); return ans; } }aint; void read(){ cin>>aint.n; int i; for(i=1;i<=aint.n;++i){ char ch; cin>>ch; if(ch=='C') aint.update(1,1,aint.n,i,1); else aint.update(1,1,aint.n,i,-1); } } void process_queries(){ int q; cin>>q; int i; for(i=1;i<=q;++i){ int st,dr; cin>>st>>dr; node ans=aint.query(1,1,aint.n,st,dr); cout<<max(ans.rez,ans.maxim)-ans.ult<<'\n'; } } int main() { read(); process_queries(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...