| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 548466 | FEDIKUS | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h" #include <vector> using namespace std; typedef long long ll; const ll maxn=2e5+10;const ll inf=1e9+10; struct node{ ll min,max,lazy;}; ll n,q,val=0;vector<pair<ll,ll> > events[maxn];vector<int> vv;node segt[4*maxn]; void ispisi(node a){ //cout<<a.min<<" "<<a.max<<" "<<a.lazy<<"\n";} node comb(node a,node b){ node ret; ret.lazy=0; ret.max=max(a.max,b.max); ret.min=min(a.min,b.min); return ret;} void push(ll ind,ll l,ll r){ if(segt[ind].lazy==0) return; if(l!=r){ segt[2*ind].min+=segt[ind].lazy; segt[2*ind].max+=segt[ind].lazy; segt[2*ind+1].min+=segt[ind].lazy; segt[2*ind+1].max+=segt[ind].lazy; segt[2*ind].lazy+=segt[ind].lazy; segt[2*ind+1].lazy+=segt[ind].lazy; } segt[ind].lazy=0;} void update(ll tl,ll tr,ll v,ll ind=1,ll l=0,ll r=q-1){ push(ind,l,r); if(tl<=l && r<=tr){ segt[ind].lazy+=v; segt[ind].min+=v; segt[ind].max+=v; return; } ll mid=l+(r-l)/2; if(tl<=mid) update(tl,tr,v,2*ind,l,mid); if(tr>mid) update(tl,tr,v,2*ind+1,mid+1,r); segt[ind]=comb(segt[2*ind],segt[2*ind+1]);} node qr(ll tl,ll tr,ll ind=1,ll l=0,ll r=q-1){ push(ind,l,r); if(tl<=l && r<=tr){ return segt[ind]; } ll mid=l+(r-l)/2; node ret={inf,-inf,0}; if(tl<=mid) ret=comb(ret,qr(tl,tr,2*ind,l,mid)); if(tr>mid) ret=comb(ret,qr(tl,tr,2*ind+1,mid+1,r)); return ret;} ll query(ll c){ ll ind=1,l=0,r=q-1,res=-1; ll tmax=-inf,tmin=inf; while(true){ //trazim prvi na kome je razlika <=c if(l==r){ if(max(tmax,segt[ind].max)-min(tmin,segt[ind].min)<=c){ res=l; tmax=max(tmax,segt[ind].max); tmin=min(tmin,segt[ind].min); } break; } if(max(tmax,segt[2*ind+1].max)-min(tmin,segt[2*ind+1].min)<=c){ res=l+(r-l)/2+1; r=l+(r-l)/2; tmax=max(tmax,segt[2*ind+1].max); tmin=min(tmin,segt[2*ind+1].min); ind=2*ind; }else{ ind=2*ind+1; l=l+(r-l)/2+1; } } if(vv[res]>0){ return val-(tmax-c); }else{ return val-tmin; }} vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { n=c.size(); q=l.size()+2; l.insert(l.begin(),1); l.insert(l.begin(),1); r.insert(r.begin(),n-1); r.insert(r.begin(),n-1); v.insert(v.begin(),-inf); v.insert(v.begin(),inf); vv=v; for(ll i=0;i<q;i++){ events[l[i]].push_back({i,v[i]}); events[r[i]+1].push_back({i,-v[i]}); } vector<int> ans(n); for(ll i=0;i<n;i++){ for(auto event:events[i]){ val+=event.second; update(event.first,q-1,event.second); } ans[i]=query(c[i]); } return ans;}