제출 #1266936

#제출 시각아이디문제언어결과실행 시간메모리
1266936glupanElection (BOI18_election)C++20
0 / 100
3 ms320 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 200005; vector<pair<ll,ll>> treePref, treeSuf; pair<ll,ll> query(int x, int lx, int rx, int l, int r) { if(lx > r or rx < l) return {0, 0}; if(lx >= l and rx <= r) return treePref[x]; int mid = (lx+rx)/2; pair<ll,ll> left = query(2*x, lx, mid, l, r); pair<ll,ll> right = query(2*x+1, mid+1, rx, l, r); return {left.first+right.first, max(left.second, left.first+right.second)}; } pair<ll,ll> Query(int x, int lx, int rx, int l, int r) { if(lx > r or rx < l) return {0, 0}; if(lx >= l and rx <= r) return treeSuf[x]; int mid = (lx+rx)/2; pair<ll,ll> left = Query(2*x, lx, mid, l, r); pair<ll,ll> right = Query(2*x+1, mid+1, rx, l, r); return {left.first+right.first, max(right.second, right.first+left.second)}; } void solve() { int n; cin >> n; string s; cin >> s; vector<int>a; for(int i=0; i<n; i++) { if(s[i] == 'C') a.push_back(-1); else a.push_back(1); } while(__builtin_popcount(n) != 1) { a.push_back(0); n++; } treePref.resize(2*n); treeSuf.resize(2*n); for(int i=0; i<n; i++) { treePref[n+i] = {a[i], a[i]}; treeSuf[n+i] = {a[i], a[i]}; } for(int i=n-1; i>0; i--) { treePref[i].first = treePref[2*i].first + treePref[2*i+1].first; treePref[i].second = max(treePref[2*i].second, treePref[2*i].first+treePref[2*i+1].second); treeSuf[i].first = treeSuf[2*i].first + treeSuf[2*i+1].first; treeSuf[i].second = max(treeSuf[2*i+1].second, treeSuf[2*i+1].first + treeSuf[2*i].second); } int q; cin >> q; while(q--) { int l,r; cin >> l >> r; l--; r--; cout << max(query(1,0,n-1,l,r).second,Query(1,0,n-1,l,r).second) << endl; } } int main() { int t=1; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...