Submission #604189

#TimeUsernameProblemLanguageResultExecution timeMemory
604189sofapudenDistributing Candies (IOI21_candies)C++17
8 / 100
1578 ms46160 KiB
#include "candies.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; struct ST { struct R { ll mn, mx; R() : mn(1ll<<60), mx(-(1ll<<60)) {} R(int x) : mn(x), mx(x) {} }; int n; vector<R> st; vector<ll> lazy; ST(int sz) : n(sz), st(4*n,0), lazy(4*n,0) {} R mer(R a, R b){ R c; c.mn = min(a.mn,b.mn); c.mx = max(a.mx,b.mx); return c; } void push(int p){ st[p].mn+=lazy[p]; st[p].mx+=lazy[p]; if((p<<1|1) < 4*n){ lazy[p<<1]+=lazy[p]; lazy[p<<1|1]+=lazy[p]; } lazy[p] = 0; } void update(int i, int j, ll v, int l, int r, int p){ push(p); if(l >= i && r <= j){ lazy[p]+=v; push(p); return; } if(l > j || r < i)return; int m = (l+r)>>1; update(i,j,v,l,m,p<<1); update(i,j,v,m+1,r,p<<1|1); st[p] = mer(st[p<<1],st[p<<1|1]); } R que(int i, int j, int l, int r, int p){ push(p); if(l >= i && r <= j)return st[p]; if(l > j || r < i)return R(); int m = (l+r)>>1; return mer(que(i,j,l,m,p<<1), que(i,j,m+1,r,p<<1|1)); } }; struct T { ll x, i; T(int _x, int _i) : x(_x), i(_i) {} }; vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { int n = c.size(); int q = l.size(); vector<vector<T>> am(n+1); for(int i = 0; i < q; ++i){ am[l[i]].emplace_back(v[i],i+1); am[r[i]+1].emplace_back(-v[i],i+1); } ST S(q+1); vector<int> ans(n,0); for(int i = 0; i < n; ++i){ for(auto x : am[i]){ S.update(x.i,q,x.x,0,q,1); } ll a = -(1ll<<60), b = (1ll<<60); int l = 0, r = q; while(l <= r){ int m = (l+r) >> 1; auto x = S.que(m,q,0,q,1); if(x.mx-x.mn >= c[i]){ a = max(a,x.mn); b = min(b,x.mx); l = m+1; } else { r = m-1; } } if(l == 0)a = 0, b = c[i]; auto x = S.que(l,q,0,q,1); if(x.mn == a)ans[i] = (int)(S.que(q,q,0,q,1).mn-a); else ans[i] = (int)(c[i] - (b - S.que(q,q,0,q,1).mn)); } 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...