#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
struct dataa{
long long prefsum = 0,prefmax = 0,prefmin = 0,lazy =0,lazymin = 0,lazymax = 0,ans = 0;
bool prefindex = 0,lazyindex = 0;
void add(long long left,long long right,long long val){
prefsum += val * (right - left + 1);
lazy += val * (right - left + 1);
if (prefsum > prefmax){
prefmax = prefsum;
prefindex = 1;
}
else if (prefsum < prefmin){
prefmin = prefsum;
prefindex = 0;
}
}
};
struct Segment_Tree{
vector<dataa>tree;
void init(long long n){
tree.resize(2*n - 1);
}
dataa combine(dataa left,dataa right){
dataa res;
res.prefsum = left.prefsum + right.prefsum;
res.prefmax = max({res.prefsum,left.prefsum + right.prefmax,left.prefmax,right.prefmax});
res.prefmin = min(res.prefsum,left.prefsum);
return res;
}
void push(long long node,long long left,long long right){
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (tree[node].lazy!=0){
tree[node + 1].add(left,mid,tree[node].lazy);
tree[z].add(mid + 1,right,tree[node].lazy);
tree[node].lazy = 0;
}
}
dataa query(long long node,long long left,long long right,long long qleft,long long qright){
if (qright<left|| qleft > right)return {0,0,0,0,0};
if (qleft<=left && qright>=right){
return tree[node];
}
push(node,left,right);
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
}
void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
if (left > uright || right < uleft) return;
if (uleft <= left && right <=uright){
tree[node].add(left,right,v);
return;
}
push(node,left,right);
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (uleft<=mid){
update(node + 1,left,mid,uleft,uright,v);
}
if (uright > mid){
update(z,mid + 1,right,uleft,uright,v);
}
tree[node] = combine(tree[node + 1],tree[z]);
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = (int)c.size();
vector<int>ans(n);
int m = (int)l.size();
vector<long long>pref(m + 1);
pref[0] = 0;
for (int i = 0;i<m;++i){
pref[i + 1] = pref[i] + v[i];
}
vector<long long>suff_max(m + 1),suff_min(m + 1);
suff_max[m] = pref[m];
suff_min[m] = pref[m];
for (int i = m - 1;i >=0;--i){
suff_max[i] = max(suff_max[i],pref[i]);
suff_min[i] = min(suff_min[i],pref[i]);
}
for (int i = 0;i<n;++i){
int left = 0,right = m;
int p = -1;
while(left<=right){
int mid = (left + right)>>1;
if (suff_max[mid] - suff_min[mid] >= c[i]){
left = mid + 1;
p = mid;
}
else right = mid - 1;
}
if (p == -1){
ans[i] = pref[m];
}
else if (suff_max[p] == pref[p]){
ans[i] = max(0LL,pref[m] - suff_max[p] + c[i]);
}
else{
ans[i] = max(0LL,pref[m] - suff_min[p]);
}
}
return ans;
}
