Submission #1052778

#TimeUsernameProblemLanguageResultExecution timeMemory
1052778MarwenElarbiDistributing Candies (IOI21_candies)C++17
29 / 100
548 ms25284 KiB
#include <bits/stdc++.h> using namespace std; #include "candies.h" #define pb push_back #define fi first #define se second const int nax=2e5+5; vector<pair<int,int>> tab; int segtree[nax*4]; long long lazy1[nax*4]; int lazy2[nax*4]; void propagate(int pos,int l,int r){ int mid=(r+l)/2; if(l==r){ segtree[pos]+=lazy1[pos]; if(lazy2[pos]) segtree[pos]=(lazy2[pos]==1 ? 0 : tab[l].fi); }else if(lazy2[pos]!=0){ lazy2[pos*2+1]=lazy2[pos*2+2]=lazy2[pos]; lazy1[pos*2+1]=lazy1[pos*2+2]=0; }else if(lazy1[pos]!=0){ if(lazy2[pos*2+1]!=0) propagate(pos*2+1,l,mid); if(lazy2[pos*2+2]!=0) propagate(pos*2+2,mid+1,r); lazy1[pos*2+1]+=lazy1[pos]; lazy1[pos*2+2]+=lazy1[pos]; } lazy1[pos]=lazy2[pos]=0; return; } void update(int pos,int l,int r,int left,int right,int type,int value){ if(l>r||l>right||r<left) return; propagate(pos,l,r); if(l>=left&&r<=right){ if(type){ lazy2[pos]=type; lazy1[pos]=0; }else{ lazy1[pos]+=value; } return; } int mid=(r+l)/2; update(pos*2+1,l,mid,left,right,type,value); update(pos*2+2,mid+1,r,left,right,type,value); } int query(int pos,int l,int r,int idx){ propagate(pos,l,r); if(l==r){ return segtree[pos]; } int mid=(r+l)/2; if(idx<=mid) return query(pos*2+1,l,mid,idx); else return query(pos*2+2,mid+1,r,idx); } 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(); for (int i = 0; i < n; ++i) tab.pb({c[i],i}); sort(tab.begin(),tab.end()); vector<int> ans(n); for (int i = 0; i < (int)l.size(); ++i) { int l=-1; int r=n; while(r-l>1){ int mid=(r+l)/2; if(v[i]>0){ if(query(0,0,n-1,mid)+v[i]>=tab[mid].fi) l=mid; else r=mid; }else{ if(query(0,0,n-1,mid)+v[i]<=0) l=mid; else r=mid; } } update(0,0,n-1,0,l,(v[i]>0 ? 2 : 1),v[i]); update(0,0,n-1,r,n-1,0,v[i]); } for (int i = 0; i < n; ++i) { ans[tab[i].se]=query(0,0,n-1,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...