#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;
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19148 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19148 KB |
Output is correct |
| 3 |
Correct |
14 ms |
19380 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19376 KB |
Output is correct |
| 5 |
Correct |
34 ms |
19504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4726 ms |
70632 KB |
Output is correct |
| 2 |
Correct |
4448 ms |
70872 KB |
Output is correct |
| 3 |
Correct |
4155 ms |
70836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19148 KB |
Output is correct |
| 2 |
Incorrect |
2087 ms |
57648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
19148 KB |
Output is correct |
| 2 |
Correct |
15 ms |
19092 KB |
Output is correct |
| 3 |
Correct |
217 ms |
48256 KB |
Output is correct |
| 4 |
Correct |
504 ms |
24728 KB |
Output is correct |
| 5 |
Correct |
993 ms |
53024 KB |
Output is correct |
| 6 |
Correct |
1034 ms |
53696 KB |
Output is correct |
| 7 |
Correct |
975 ms |
54272 KB |
Output is correct |
| 8 |
Correct |
1073 ms |
52924 KB |
Output is correct |
| 9 |
Correct |
936 ms |
54400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
19148 KB |
Output is correct |
| 2 |
Correct |
11 ms |
19148 KB |
Output is correct |
| 3 |
Correct |
14 ms |
19380 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19376 KB |
Output is correct |
| 5 |
Correct |
34 ms |
19504 KB |
Output is correct |
| 6 |
Correct |
4726 ms |
70632 KB |
Output is correct |
| 7 |
Correct |
4448 ms |
70872 KB |
Output is correct |
| 8 |
Correct |
4155 ms |
70836 KB |
Output is correct |
| 9 |
Correct |
11 ms |
19148 KB |
Output is correct |
| 10 |
Incorrect |
2087 ms |
57648 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
