Submission #504552

#TimeUsernameProblemLanguageResultExecution timeMemory
504552arthur_nascimentoDistributing Candies (IOI21_candies)C++17
0 / 100
5034 ms224828 KiB
#include "candies.h" #include <cassert> #include <cstdio> #include <vector> #include <bits/stdc++.h> using namespace std; #define maxn 200200 #define mid ((ini+fim)/2) #define pb push_back #define ll long long #define search iwfew #define debug printf ll T[4*maxn]; ll mn[4*maxn]; ll mx[4*maxn]; int pos_mn[4*maxn]; ll lazy[4*maxn]; int n,q; void refresh(int ini,int fim,int p){ if(ini < fim){ lazy[2*p] += lazy[p]; lazy[2*p+1] += lazy[p]; } mn[p] += lazy[p]; mx[p] += lazy[p]; lazy[p] = 0; } void merge(int ini,int fim,int p){ mx[p] = max(mx[2*p],mx[2*p+1]); mn[p] = min(mn[2*p],mn[2*p+1]); pos_mn[p] = pos_mn[2*p]; if(mn[2*p+1] < mn[2*p]) pos_mn[p] = pos_mn[2*p+1]; T[p] = mx[p] - mn[p]; } void bd(int ini,int fim,int p){ if(ini == fim){ pos_mn[p] = ini; return; } bd(ini,mid,2*p); bd(mid+1,fim,2*p+1); pos_mn[p] = ini; } int search(int ini,int fim,int p,ll d,ll mnr=0,ll mxr=0,ll hasr=0){ refresh(ini,fim,p); if(ini == fim) return ini; ll gapR = T[2*p+1]; if(hasr) gapR = max(gapR, mxr - mn[2*p+1]); if(hasr) gapR = max(gapR, mx[2*p+1] - mnr); if(gapR > d) return search(mid+1,fim,2*p+1,d,mnr,mxr,hasr); ll mn_ = mn[2*p+1]; if(hasr) mn_ = min(mn_, mnr); ll mx_ = mx[2*p+1]; if(hasr) mx_ = max(mx_, mxr); return search(ini,mid,2*p,d,mn_,mx_,1); } ll get(int ini,int fim,int p,int pos){ refresh(ini,fim,p); if(ini > pos || fim < pos) return 0; if(ini == fim) return mx[p]; ll ret = get(ini,mid,2*p,pos) + get(mid+1,fim,2*p+1,pos); merge(ini,fim,p); return ret; } void upd(int ini,int fim,int p,int l,int r,int x){ refresh(ini,fim,p); if(l > fim || r < ini) return; if(ini >= l && fim <= r){ lazy[p] += x; refresh(ini,fim,p); return; } upd(ini,mid,2*p,l,r,x); upd(mid+1,fim,2*p+1,l,r,x); merge(ini,fim,p); } vector<int> Ti[4*maxn]; void updi(int ini,int fim,int p,int a,int b,int k){ if(ini > b) return; if(fim < a) return; if(ini >= a && fim <= b){ Ti[p].pb(k); return; } updi(ini,mid,2*p,a,b,k); updi(mid+1,fim,2*p+1,a,b,k); } vector<int> ans; vector<int> l,r,add,cap; void go(int ini,int fim,int p){ debug("go %d~%d\n",ini,fim); for(int a : Ti[p]){ upd(0,q,1,a+1,q,add[a]); debug("add %d at %d\n",add[a],a); } if(ini == fim){ int c = cap[ini]; int beg = 0; debug("qry %d cap %d\n",ini,c); if(T[1] > c) beg = 1 + search(0,q,1,c); beg = max(beg,pos_mn[1]); ll delta = get(0,q,1,q) - get(0,q,1,beg); debug("get %d = %lld\n",q,get(0,q,1,q)); debug("get %d = %lld\n",beg,get(0,q,1,beg)); debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta); if(delta > 0) ans[ini] = delta; else ans[ini] = cap[ini] + delta; if(delta == 0 && beg > 0 && get(0,q,1,beg-1) > get(0,q,1,beg)) ans[ini] = 0; } if(ini < fim) go(ini,mid,2*p); if(ini < fim) go(mid+1,fim,2*p+1); for(int a : Ti[p]){ upd(0,q,1,a+1,q,-add[a]); debug("rem %d at %d\n",add[a],a); } } std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> L, std::vector<int> R, std::vector<int> v) { n = c.size(); q = L.size(); cap = c; l = L; r = R; add = v; for(int i=0;i<q;i++) updi(0,n-1,1,l[i],r[i],i); bd(0,q-1,1); for(int i=0;i<n;i++) ans.pb(0); go(0,n-1,1); return ans; }

Compilation message (stderr)

candies.cpp: In function 'void go(int, int, int)':
candies.cpp:151:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  151 |   debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
      |                 ~^                              ~~~~
      |                  |                                 |
      |                  int                               long long int
      |                 %lld
#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...