제출 #1267225

#제출 시각아이디문제언어결과실행 시간메모리
1267225akmuhammet_sElection (BOI18_election)C++20
0 / 100
1 ms320 KiB
#include "bits/stdc++.h" using namespace std; #define mod 998244353 #define ll long long #define N 24 #define maxn 200005 void solve(){ int n; cin>>n; string s; cin>>s; int sq=sqrt(n); int p[n+5],pg[n+5],ss[n+5],ps[n+5]; int cur=0,mn=1e9; for(int i=0; i<s.size(); i++){ if(s[i]=='C') cur++; else cur--; p[i]=cur; mn=min(mn,cur); if(i%sq==(sq-1)){ pg[i/sq]=mn; mn=1e9; } } cur=0; for(int i=0; i<s.size(); i++){ if(s[s.size()-1-i]=='C') cur++; else cur--; ss[i]=cur; mn=min(mn,cur); if(i%sq==(sq-1)){ ps[i/sq]=mn; mn=1e9; } } int q; cin>>q; while(q--){ int l,r; cin>>l>>r; int x=1e9; for(int i=l-1; i<r; i++){ if(i%sq==0 and (i+sq)<=r){ x=min(x,pg[i/sq]); i=i+sq-1; }else{ x=min(x,p[i]); } } if(l>1){ x-=ss[l-2]; } int ans=x; x=1e9; int yl=n-r,rr=n-l; for(int i=yl; i<=rr; i++){ if(i%sq==0 and (i+sq)<=r){ x=min(x,ps[i/sq]); i=i+sq-1; }else{ x=min(x,ss[i]); } } if(r<n){ x-=ss[n-r-1]; } ans=min(ans,x); cout<<abs(ans)<<'\n'; } } int main(){ // freopen("in.txt","w",stdout); // freopen("out.txt","r",stdin); ios_base::sync_with_stdio(0); cin.tie(0); ll t=1; // cin>>t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...