제출 #504670

#제출 시각아이디문제언어결과실행 시간메모리
504670arthur_nascimento사탕 분배 (IOI21_candies)C++17
40 / 100
4726 ms70872 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 ll T[4*maxn]; ll mn[4*maxn]; ll mx[4*maxn]; int pos_mn[4*maxn]; int pos_mx[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]; pos_mx[p] = pos_mx[2*p]; if(mx[2*p+1] > mx[2*p]) pos_mx[p] = pos_mx[2*p+1]; T[p] = mx[p] - mn[p]; debug("pos_mx[%d] := %d\n",p,pos_mx[p]); } void bd(int ini,int fim,int p){ if(ini == fim){ pos_mn[p] = ini; pos_mx[p] = ini; return; } bd(ini,mid,2*p); bd(mid+1,fim,2*p+1); pos_mn[p] = ini; pos_mx[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; refresh(mid+1,fim,2*p+1); merge(ini,fim,p); 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 vm, vM; int pm, pM; void qr(int ini,int fim,int p,int l,int r){ debug("qr %d~%d p %d\n",ini,fim,p); refresh(ini,fim,p); if(ini > r || fim < l) return; if(ini >= l && fim <= r){ if(mn[p] < vm){ vm = mn[p]; pm = pos_mn[p]; } debug("mx %lld po %d\n",mx[p],pos_mx[p]); if(mx[p] > vM){ vM = mx[p]; pM = pos_mx[p]; } return; } qr(ini,mid,2*p,l,r); qr(mid+1,fim,2*p+1,l,r); merge(ini,fim,p); } int get_min(int a){ vm = 1e18; vM = -1e18; qr(0,q,1,a,q); return pm; } int get_max(int a){ vm = 1e18; vM = -1e18; qr(0,q,1,a,q); debug("mx (%d) = %d\n",a,pM); return pM; } 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){ ll 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-1,get(0,q,1,beg-1)); 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(beg > 0){ if(get(0,q,1,beg-1) >= get(0,q,1,beg)) { beg = get_min(beg); delta = get(0,q,1,q) - get(0,q,1,beg); ans[ini] = delta; } else { beg = get_max(beg); delta = get(0,q,1,q) - get(0,q,1,beg); ans[ini] = c + delta; } } else ans[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); for(int i=0;i<n;i++) ans.pb(0); go(0,n-1,1); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'void merge(int, int, int)':
candies.cpp:48:8: warning: left operand of comma operator has no effect [-Wunused-value]
   48 |  debug("pos_mx[%d] := %d\n",p,pos_mx[p]);
      |        ^~~~~~~~~~~~~~~~~~~~
candies.cpp:48:39: warning: right operand of comma operator has no effect [-Wunused-value]
   48 |  debug("pos_mx[%d] := %d\n",p,pos_mx[p]);
      |                                       ^
candies.cpp: In function 'void qr(int, int, int, int, int)':
candies.cpp:91:8: warning: left operand of comma operator has no effect [-Wunused-value]
   91 |  debug("qr %d~%d p %d\n",ini,fim,p);
      |        ^~~~~~~~~~~~~~~~~
candies.cpp:91:30: warning: right operand of comma operator has no effect [-Wunused-value]
   91 |  debug("qr %d~%d p %d\n",ini,fim,p);
      |                              ^~~
candies.cpp:91:34: warning: right operand of comma operator has no effect [-Wunused-value]
   91 |  debug("qr %d~%d p %d\n",ini,fim,p);
      |                                  ^
candies.cpp:102:9: warning: left operand of comma operator has no effect [-Wunused-value]
  102 |   debug("mx %lld po %d\n",mx[p],pos_mx[p]);
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:102:31: warning: right operand of comma operator has no effect [-Wunused-value]
  102 |   debug("mx %lld po %d\n",mx[p],pos_mx[p]);
      |                           ~~~~^
candies.cpp: In function 'int get_max(int)':
candies.cpp:129:8: warning: left operand of comma operator has no effect [-Wunused-value]
  129 |  debug("mx (%d) = %d\n",a,pM);
      |        ^~~~~~~~~~~~~~~~
candies.cpp:129:27: warning: right operand of comma operator has no effect [-Wunused-value]
  129 |  debug("mx (%d) = %d\n",a,pM);
      |                           ^~
candies.cpp: In function 'void go(int, int, int)':
candies.cpp:182:8: warning: left operand of comma operator has no effect [-Wunused-value]
  182 |  debug("go %d~%d\n",ini,fim);
      |        ^~~~~~~~~~~~
candies.cpp:182:25: warning: right operand of comma operator has no effect [-Wunused-value]
  182 |  debug("go %d~%d\n",ini,fim);
      |                         ^~~
candies.cpp:186:9: warning: left operand of comma operator has no effect [-Wunused-value]
  186 |   debug("add %d at %d\n",add[a],a);
      |         ^~~~~~~~~~~~~~~~
candies.cpp:195:9: warning: left operand of comma operator has no effect [-Wunused-value]
  195 |   debug("qry %d cap %d\n",ini,c);
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:195:31: warning: right operand of comma operator has no effect [-Wunused-value]
  195 |   debug("qry %d cap %d\n",ini,c);
      |                               ^
candies.cpp:204:9: warning: left operand of comma operator has no effect [-Wunused-value]
  204 |   debug("get %d = %lld\n",q,get(0,q,1,q));
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:204:40: warning: right operand of comma operator has no effect [-Wunused-value]
  204 |   debug("get %d = %lld\n",q,get(0,q,1,q));
      |                                        ^
candies.cpp:205:9: warning: left operand of comma operator has no effect [-Wunused-value]
  205 |   debug("get %d = %lld\n",beg-1,get(0,q,1,beg-1));
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:205:30: warning: right operand of comma operator has no effect [-Wunused-value]
  205 |   debug("get %d = %lld\n",beg-1,get(0,q,1,beg-1));
      |                           ~~~^~
candies.cpp:206:9: warning: left operand of comma operator has no effect [-Wunused-value]
  206 |   debug("get %d = %lld\n",beg,get(0,q,1,beg));
      |         ^~~~~~~~~~~~~~~~~
candies.cpp:206:44: warning: right operand of comma operator has no effect [-Wunused-value]
  206 |   debug("get %d = %lld\n",beg,get(0,q,1,beg));
      |                                            ^
candies.cpp:208:9: warning: left operand of comma operator has no effect [-Wunused-value]
  208 |   debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:208:52: warning: right operand of comma operator has no effect [-Wunused-value]
  208 |   debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
      |                                                 ~~~^
candies.cpp:208:58: warning: right operand of comma operator has no effect [-Wunused-value]
  208 |   debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
      |                                                          ^~~~~
candies.cpp:241:9: warning: left operand of comma operator has no effect [-Wunused-value]
  241 |   debug("rem %d at %d\n",add[a],a);
      |         ^~~~~~~~~~~~~~~~
#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...