#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
struct UPDATE {
long long l,r,v,p;
};
int l,r;
long long val;
vector<long long>mn, mx, mn_lazy, mx_lazy, st;
long long sum_query(int i, int j, int p) {
if(i > r || j < l)
return 0;
if(i >= l && j <= r)
return st[p];
int mid = (i+j)/2;
return sum_query(i, mid, 2*p) + sum_query(mid+1, j, 2*p+1);
}
void sum_update(int i, int j, int p) {
if(i > r || j < l)
return;
if(i == j) {
st[p] += val;
return;
}
int mid = (i+j)/2;
sum_update(i, mid, 2*p);
sum_update(mid+1, j, 2*p+1);
st[p] = st[2*p] + st[2*p+1];
}
long long min_query(int i, int j, int p) {
if(i >= l && j <= r)
return mn[p] + mn_lazy[p];
mn_lazy[2*p] += mn_lazy[p];
mn_lazy[2*p+1] += mn_lazy[p];
mn[p] += mn_lazy[p];
mn_lazy[p] = 0;
int mid = (i+j)/2;
long long ret = LLONG_MAX;
if(l <= mid)
ret = min_query(i, mid, 2*p);
if(r > mid)
ret = min(ret, min_query(mid+1, j, 2*p+1));
return ret;
}
long long max_query(int i, int j, int p) {
if(i >= l && j <= r)
return mx[p] + mx_lazy[p];
//cout << i << ' ' << j << '\n';
mx_lazy[2*p] += mx_lazy[p];
mx_lazy[2*p+1] += mx_lazy[p];
mx[p] += mx_lazy[p];
mx_lazy[p] = 0;
int mid = (i+j)/2;
long long ret = LLONG_MIN;
if(l <= mid)
ret = max_query(i, mid, 2*p);
if(r > mid)
ret = max(ret, max_query(mid+1, j, 2*p+1));
return ret;
}
pair<long long, long long> update(int i, int j, int p) {
if(i > r || j < l)
return {mn[p] + mn_lazy[p], mx[p] + mx_lazy[p]};
if(i >= l && j <= r) {
mn_lazy[p] += val;
mx_lazy[p] += val;
return {mn[p] + mn_lazy[p], mx[p] + mx_lazy[p]};
}
mn_lazy[2*p] += mn_lazy[p];
mn_lazy[2*p+1] += mn_lazy[p];
mn_lazy[p] = 0;
mx_lazy[2*p] += mx_lazy[p];
mx_lazy[2*p+1] += mx_lazy[p];
mx_lazy[p] = 0;
int mid = (i+j)/2;
pair<long long, long long> ret = {LLONG_MAX, LLONG_MIN};
ret = update(i, mid, 2*p);
auto z = update(mid+1, j, 2*p+1);
ret.first = min(ret.first, z.first);
ret.second = max(ret.second, z.second);
mn[p] = ret.first, mx[p] = ret.second;
return ret;
}
vector<int>distribute_candies(vector<int>c, vector<int>L, vector<int>R, vector<int>V) {
const int n = (int)c.size();
const int m = (int)L.size();
long long value = 0;
mn.resize(8*m, 0);
mx.resize(8*m, 0);
mn_lazy.resize(8*m, 0);
mx_lazy.resize(8*m, 0);
st.resize(8*m, 0);
vector<int>ans(n);
vector<vector<UPDATE>>upd(n+1);
for(int i = 0 ; i < m ; i++) {
UPDATE Upd;
Upd.l = L[i], Upd.r = R[i], Upd.v = V[i]; Upd.p = i;
upd[L[i]].push_back(Upd);
upd[R[i]+1].push_back(Upd);
}
//
for(int i = 0 ; i < n ; i++) {
for(auto z : upd[i]) {
if(z.l == i) {
val = z.v;
l = z.p, r = m-1;
value += z.v;
update(0, m-1, 1);
l = 0;
//if(!i)cout << min_query(0, m-1, 1) << '-';
l = r = z.p;
val = z.v;
sum_update(0, m-1, 1);
} else {
val = -z.v;
l = z.p, r = m-1;
value -= z.v;
update(0, m-1, 1);
l = r = z.p;
val = -z.v;
sum_update(0, m-1, 1);
}
}
int p = m+1;
int le = 0, re = m-1;
while(le <= re) {
int mid = (le+re)/2;
l = mid, r = m-1;
long long suff_max = max_query(0, m-1, 1);
long long suff_min = min_query(0, m-1, 1);
//cout << mid << ' ' << suff_max << ' ' << suff_min << '\n';
if(suff_max - suff_min > c[i]) {
le = mid+1, p = mid;
} else {
re = mid-1;
}
}
if(p == m+1) {
l = 0, r = m-1;
//cout << max_query(0, m-1, 1) << ' ';
if(max_query(0, m-1, 1) > c[i]) {
ans[i] = max(c[i] - (max_query(0, m-1, 1) - value), 0LL);
continue;
}
l = 0;
ans[i] = value - min(0LL,min_query(0, m-1, 1));
continue;
}
// 0 0 0
// 10 15 13
// 0 4 13
// 20 20 20
// 9 9 9
l = 0, r = p;
long long value_p = sum_query(0, m-1, 1);
l = p, r = m-1;
//cout << i << ' ' << value << ' ' << value_p << ' ' << min_query(0, m-1, 1) << ' ' << max_query(0, m-1, 1) << '\n';
if(value_p == min_query(0, m-1, 1)) { // smaller side
ans[i] = max(c[i] - (max_query(0, m-1, 1) - value), 0LL);
} else {
ans[i] = max(value - min_query(0, m-1, 1), 0LL);
}
}
return ans;
}
