Submission #384511

#TimeUsernameProblemLanguageResultExecution timeMemory
384511PetiElection (BOI18_election)C++14
0 / 100
4 ms492 KiB
#include <bits/stdc++.h> using namespace std; struct segment_tree{ vector<int> st, stadd; int maxn = 0; void init(int n){ maxn = n; while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn)); st.assign(2*maxn, 0); stadd.assign(2*maxn, 0); return; } void pont_update(int x, int l, int r){ if(l+1 == r){ st[x] += stadd[x]; stadd[x] = 0; return; } st[x] = min(st[2*x+1], st[2*x+2]) + stadd[x]; return; } void propagate(int x, int l, int r){ if(l+1 == r){ pont_update(x, l, r); return; } int m = (l+r)/2; stadd[2*x+1] += stadd[x]; stadd[2*x+2] += stadd[x]; stadd[x] = 0; pont_update(2*x+1, l, m); pont_update(2*x+2, m, r); pont_update(x, l, r); return; } void add(int L, int R, int c, int x, int l, int r){ propagate(x, l, r); if(r <= L || R <= l) return; if(L <= l && r <= R){ stadd[x] += c; pont_update(x, l, r); return; } int m = (l+r)/2; add(L, R, c, 2*x+1, l, m); add(L, R, c, 2*x+2, m, r); return; } void add(int l, int r, int c){ add(l, r, c, 0, 0, maxn); return; } int ertek(int L, int R, int x, int l, int r){ propagate(x, l, r); if(r <= L || R <= l) return (int)1e9; if(L <= l && r <= R) return st[x]; int m = (l+r)/2; return min(ertek(L, R, 2*x+1, l, m), ertek(L, R, 2*x+2, m, r)); } int ertek(int l, int r){ return ertek(l, r, 0, 0, maxn); } int elem(int ind, int x, int l, int r){ propagate(x, l, r); if(l+1 == r) return st[x]; int m = (l+r)/2; if(ind < m) return elem(ind, 2*x+1, l, m); return elem(ind, 2*x+2, m, r); } int elem(int x){ return elem(x, 0, 0, maxn); } }; struct segment_tree2{ vector<int> st; int maxn = 0; void init(int n){ maxn = n; while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn)); st.assign(2*maxn, 0); return; } void update(int x, int c){ st[x+maxn] = c; for(int i = (x+maxn)>>1; i > 0; i >>= 1) st[i] = st[2*i] + st[2*i+1]; return; } int ertek(int L, int R, int x, int l, int r){ if(r <= L || R <= l) return 0; if(L <= l && r <= R) return st[x]; return ertek(L, R, 2*x, l, (l+r)/2) + ertek(L, R, 2*x+1, (l+r)/2, r); } int ertek(int l, int r){ return ertek(l, r, 1, 0, maxn); } }; int main() { cin.sync_with_stdio(false); cin.tie(0); int n, q; string s; cin>>n; cin>>s; cin>>q; vector<vector<pair<int, int>>> v(n); for(int i = 0; i < q; i++){ int l, r; cin>>l>>r; v[l-1].push_back(make_pair(r-1, i)); } vector<int> kov(n); iota(kov.begin(), kov.end(), 1); vector<int> ki(q); segment_tree st; segment_tree2 st3; st.init(n+1); st3.init(n+1); vector<bool> volt(n, false); for(int i = 0; i < n; i++){ if(s[i] == 'C') volt[i] = true; else st3.update(i, 1); } int x = n-1, last = n-1; for(int i = n-1; i >= 0; i--){ if(s[i] == 'C'){ x = i; while(x < n && volt[x]) x++; if(x < n){ /*if(last != x) kov[last] = x;*/ volt[x] = true; st3.update(x, 0); st.add(0, x+1, -1); } st.add(0, i+1, 1); } else x = last = i; for(pair<int, int> temp : v[i]) ki[temp.second] = max(0, st.elem(temp.first+1)-st.ertek(i, temp.first+1)) + st3.ertek(i, temp.first+1); } for(int x : ki) cout<<x<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...