Submission #611852

#TimeUsernameProblemLanguageResultExecution timeMemory
611852amunduzbaevElection (BOI18_election)C++17
82 / 100
3034 ms111644 KiB
#include "bits/stdc++.h" using namespace std; #define ar array typedef int64_t ll; #define her cerr<<"here"<<endl; const int N = 7e5 + 5; const int B = 710; int a[N], pref[N], suff[N], mx[2][B + 1], in[B][B + 1][B + 1]; int pos[B][B + 1], sos[B][B + 1], used[N]; int pv[B], sv[B]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; string s; cin >> s; for(int b=0;b * B<n;b++){ int l = b * B, r = min(n, (b + 1) * B); memset(pos[b], -1, sizeof pos[b]); for(int i=l;i<r;i++){ if(s[i] == 'C') pref[i]--; else pref[i]++; if(i + 1 < r) pref[i + 1] = pref[i]; mx[0][b] = max(mx[0][b], pref[i]); if(pref[i] > 0 && pos[b][pref[i]] == -1) pos[b][pref[i]] = i; } memset(sos[b], -1, sizeof sos[b]); for(int i=r-1;i>=l;i--){ suff[i] = suff[i + 1]; if(s[i] == 'C') suff[i]--; else suff[i]++; mx[1][b] = max(mx[1][b], suff[i]); if(suff[i] > 0 && sos[b][suff[i]] == -1) sos[b][suff[i]] = i; } mx[1][b]++, mx[0][b]++; for(int i=mx[0][b] - 1;i>0;i--){ int cc = 0, r = i; for(int j=mx[1][b] - 1;j>0;j--){ while(r < mx[0][b] && pos[b][r] < sos[b][j]) r++; if(r < mx[0][b]) cc++, r++; in[b][i][j] = cc; } } } int q; cin >> q; for(int i=0;i<q;i++){ int l, r; cin >> l >> r; l--, r--; int l_ = l / B, r_ = r / B; if(l_ == r_){ int sum = 0, x = 1, cnt = 0; for(int i=l;i<=r;i++){ if(s[i] == 'C') sum--; else sum++; if(sum == x) used[i] = 1, cnt++, x++; } int is = 0; sum = 0, x = 1; for(int i=r;i>=l;i--){ if(s[i] == 'C') sum--; else sum++; if(used[i]) is++, used[i] = 0; if(sum == x){ if(!is) cnt++; else is--; x++; } } cout<<cnt<<"\n"; for(int i=l;i<=r;i++) used[i] = 0; continue; } //~ cout<<l<<" "<<(l_ + 1) * B - 1<<" <-\n"; int sum = 0, x = 1, cnt = 0; for(int i=l;i<(l_ + 1) * B;i++){ if(s[i] == 'C') sum--; else sum++; //~ cout<<i<<" "<<sum<<" "<<x<<"\n"; if(sum == x) used[i] = 1, cnt++, x++; } for(int b=l_+1;b<r_;b++){ if(mx[0][b] > x - sum) pv[b] = x - sum; else pv[b] = mx[0][b]; //~ cout<<b<<" "<<mx[0][b]<<" "<<pv[b]<<" <-\n"; x += (mx[0][b] - pv[b]); cnt += (mx[0][b] - pv[b]); sum += suff[b * B]; } for(int i=r_ * B;i<=r;i++){ if(s[i] == 'C') sum--; else sum++; //~ cout<<i<<" "<<sum<<" "<<x<<"\n"; if(sum == x) used[i] = 1, cnt++, x++; } //~ cout<<cnt<<" : "; int is = 0; sum = 0, x = 1; for(int i=r;i>=r_*B;i--){ if(s[i] == 'C') sum--; else sum++; if(used[i]) is++, used[i] = 0; if(sum == x){ if(!is) cnt++; else is--; x++; } } //~ cout<<cnt<<" : "; for(int b=r_-1;b>l_;b--){ if(mx[1][b] > x - sum){ sv[b] = x - sum; x += (mx[1][b] - x + sum); } else { sv[b] = mx[1][b]; } is += in[b][pv[b]][sv[b]]; //~ cout<<is<<" "<<mx[1][b]<<" "<<sv[b]<<"\n"; cnt += max(0, mx[1][b] - sv[b] - is); is -= min(is, mx[1][b] - sv[b]); is += (mx[0][b] - pv[b] - in[b][pv[b]][sv[b]]); sum += suff[b * B]; } //~ cout<<cnt<<" : "; for(int i=(l_ + 1) * B - 1;i>=l;i--){ if(s[i] == 'C') sum--; else sum++; if(used[i]) is++, used[i] = 0; if(sum == x){ if(!is) cnt++; else is--; x++; } } cout<<cnt<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...