#include <iostream>
#include <vector>
using namespace std;
#include "candies.h"
#define ll long long
struct segTree{
ll l;
ll r;
ll mn;
ll mx;
ll lazy;
segTree * lc, * rc;
segTree(ll indx){
l = r = indx;
mn = mx = 0;
lazy = 0;
lc = rc = nullptr;
}
segTree(segTree*le, segTree*ri){
lc = le;
rc = ri;
l = le->l;
r = ri->r;
mn = mx = lazy = 0;
}
};
ll c;
segTree * build(ll l, ll r){
if(l == r) return new segTree(l);
ll mid = (l+r)/2;
return new segTree(build(l, mid), build(mid+1, r));
}
void clamp(segTree * st){
if(st->l == st->r){
st->mn = st->mx = max((ll)0, min(c, st->mn+st->lazy));
st->lazy = 0;
return;
}
if(st->mn+st->lazy < 0 && st->mx+st->lazy > 0){
st->lc->lazy += st->lazy;
st->rc->lazy += st->lazy;
clamp(st->lc); clamp(st->rc);
st->lazy = 0;
st->mn = min(st->lc->mn, st->rc->mn);
st->mx = max(st->lc->mx, st->rc->mx);
}
else if(st->mx +st->lazy < 0){
st->lazy = 0;
st->mn = 0;
}
if(st->mx > c + st->lazy && st->mn < c + st->lazy){
st->lc->lazy += st->lazy;
st->rc->lazy += st->lazy;
clamp(st->lc); clamp(st->rc);
st->lazy = 0;
st->mn = min(st->lc->mn, st->rc->mn);
st->mx = max(st->lc->mx, st->rc->mx);
}
else if(st->mn +st->lazy > c){
st->lazy = 0;
st->mx = c;
}
}
void update(segTree * st, ll l, ll r, ll x){
if(l == st->l && r == st->r){
st->lazy = x;
clamp(st);
return;
}
ll mid = (st->l + st->r)/2;
if(l <= mid) update(st->lc, l, min(r, mid), x);
if(r > mid) update(st->rc, max(l, mid+1), r, x);
st->lazy = 0;
st->mn = min(st->lc->mn, st->rc->mn);
st->mx = max(st->lc->mx, st->rc->mx);
}
ll query(segTree * st, ll ind){
if(st->l == st->r) return max((ll)0, min(st->mn+st->lazy, c));
ll mid = (st->l + st->r)/2;
if(st->lazy){
st->lc->lazy += st->lazy;
st->rc->lazy += st->lazy;
st->lazy = 0;
}
if(ind <= mid) return query(st->lc, ind);
else return query(st->rc, ind);
}
vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v){
c = C[0];
segTree * seg = build(0, C.size()-1);
for(ll i = 0; i<l.size(); i++){
update(seg, l[i], r[i], v[i]);
//clamp(seg);
}
vector<int> ans(C.size(), 0);
for(ll i = 0; i<C.size(); i++) ans[i] = query(seg, i);
return ans;
}
