Submission #485087

#TimeUsernameProblemLanguageResultExecution timeMemory
485087wwddDistributing Candies (IOI21_candies)C++17
100 / 100
793 ms37104 KiB
#include "candies.h" #include <vector> #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vl; typedef pair<ll,ll> pl; // bruh class ST { private: int n,h; vl sa,sb,lz; const ll STA = -1LL<<62; const ll STB = 1LL<<62; int log2(int v) { if(v <= 1) return 1; return log2(v/2)+1; } void ap(int p, ll val) { sa[p] += val; sb[p] += val; if(p < n) {lz[p] += val;} } void build(int p) { while(p > 1) { p >>= 1; if(p >= n) continue; sa[p] = max(sa[p<<1],sa[p<<1|1])+lz[p]; sb[p] = min(sb[p<<1],sb[p<<1|1])+lz[p]; } } void psh(int p) { for(int s=h;s>0;s--) { int i = p>>s; if(lz[i] != 0) { ap(i<<1,lz[i]); ap(i<<1|1,lz[i]); lz[i] = 0; } } } public: ST(int _n) { n = _n; h = log2(n); sa.assign(2*n,0); sb.assign(2*n,0); lz.assign(n,0); } void up(int l, int r, ll val) { if(l >= r) return; l += n;r += n; int li = l,ri = r; for(;l<r;l>>=1,r>>=1) { if(l&1) {ap(l++,val); } if(r&1) {ap(--r,val); } } build(li);build(ri-1); } pl get(int l, int r) { l += n;r += n; psh(l);psh(r-1); ll ra = STA; ll rb = STB; for(;l<r;l>>=1,r>>=1) { if(l&1) { ra = max(ra,sa[l]); rb = min(rb,sb[l]); l++; } if(r&1) { --r; ra = max(ra,sa[r]); rb = min(rb,sb[r]); } } return {ra,rb}; } }; std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { int n = c.size(); l.insert(l.begin(),0); l.insert(l.begin(),0); r.insert(r.begin(),n-1); r.insert(r.begin(),n-1); v.insert(v.begin(),-(1e9+7)); v.insert(v.begin(),1e9+7); ll q = l.size(); ST st(q); vector<vector<pl> > ops(n+1); for(int i=0;i<q;i++) { ops[l[i]].emplace_back(i,v[i]); ops[r[i]+1].emplace_back(i,-v[i]); } std::vector<int> ans(n); for(int i=0;i<n;i++) { for(const auto& op: ops[i]) { st.up(op.first,q,op.second); } ll fv = st.get(q-1,q).first; ll sv = 0,ev = q-1; ll ls = 0; while(sv <= ev) { ll m = (sv+ev)/2; pl val = st.get(m,q); if(val.first-val.second > c[i]) { ls = m; sv = m+1; } else { ev = m-1; } } pl val = st.get(ls,q); ll los = st.get(ls,ls+1).first; if(los == val.first) { ans[i] = fv-val.second; } else { ans[i] = fv-val.first+c[i]; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...