제출 #1082570

#제출 시각아이디문제언어결과실행 시간메모리
1082570BLOBVISGODElection (BOI18_election)C++17
0 / 100
2 ms600 KiB
#include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=(a); i<(b); ++i) #define all(x) x.begin(),x.end() #define sz(x) int(x.size()) typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; struct segtree{ struct node{ int sum=0, minpref=0, id=0; node operator+(node b){ node ans; ans.sum = sum + b.sum; if (sum + b.minpref < minpref){ ans.minpref = sum + b.minpref; ans.id = b.id; }else{ ans.minpref = minpref; ans.id = id; } return ans; } }; int n; vector<node> a; segtree(vi b){ n = 1; while(n < sz(b)) n*=2; a.resize(n*2); rep(i,0,sz(b)){ a[n+i] = {b[i],b[i],i}; } for (int i = n-1; i>0; --i) a[i] = a[i*2]+a[i*2+1]; } node query(int id, int l, int r, int ql, int qr){ if (l >= ql and r <= qr) return a[id]; else if (r <= ql or l >= qr) return {}; else{ int mid = (l+r)/2; return query(id*2,l,mid,ql,qr)+query(id*2+1,mid,r,ql,qr); } } node get(int l, int r){ return query(1,0,n,l,r); } }; int main(){ cin.tie(NULL),cin.sync_with_stdio(false); int n,q; cin >> n; string s; cin >> s; vi a(n),b; rep(i,0,n) a[i] = (s[i]=='C')?1:-1; b = a; reverse(all(b)); // i -> n-1-i segtree LtoR(a), RtoL(b); cin >> q; while(q--){ int l,r; cin >> l >> r; // [l,r] l--,r--; // LtoR : l r+1 // RtoL : n-1-r n-l auto ansL = LtoR.get(l,r+1), ansR = RtoL.get(n-1-r,n-l); int L = n-1-ansR.id, R = ansL.id; if (L > R) cout << max(0,-ansR.minpref)+max(0,-ansL.minpref) << '\n'; else{ auto ansL2 = LtoR.get(l,L); cout << max(0,-ansL2.minpref)+max(0,-ansR.minpref) << '\n'; } } } /* 1 1 CCCTTTTTTCC 3 1 11 4 9 1 6 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...