#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>st;
int l,r;
int lim;
int query(int i, int j, int p) {
if(i > l || j < l)
assert(0);
if(i == j) {
int ans = 0;
for(auto z : st[p]) {
if(z > 0) {
ans += min(z, lim - ans);
} else ans -= min(-z, ans);
}
return ans;
}
int mid = (i+j)/2;
int ans = (i <= l && mid >= l ? query(i,mid,2*p) : query(mid+1,j,2*p+1));
for(auto z : st[p]) {
if(z > 0) {
ans += min(z, lim - ans);
} else ans -= min(-z, ans);
}
return ans;
}
int val;
void update(int i, int j, int p) {
if(i > r || j < l)
return;
if(i >= l && j <= r) {
int app = val;
while(!st[p].empty()) {
if((st[p].back() >= 0 && val >= 0) || (st[p].back() <= 0 && val <= 0))
app += st[p].back(),st[p].pop_back();
else break;
}
st[p].push_back(app);
return;
}
for(auto z : st[p])
st[2*p].push_back(z),st[2*p+1].push_back(z);
st[p].clear();
int mid = (i+j)/2;
update(i,mid,2*p),update(mid+1,j,2*p+1);
}
vector<int> distribute_candies(vector<int> c, vector<int> le, vector<int> ri, vector<int> v) {
const int n = (int)c.size();
const int q = (int)v.size();
st.resize(8*n);
for(int i = 0 ; i < q ; i++) {
val = v[i];
l = le[i], r = ri[i];
update(0, n-1, 1);
}
vector<int>ans;
for(int i = 0 ; i < n ; i++) {
lim = c[i];
l = i;
ans.push_back(query(0,n-1,1));
}
return ans;
}
