#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn = 2e5+10;
ll mi[mn*4], ma[mn*4], laz[mn*4];
void prop(int x){
if(!laz[x]) return;
mi[x] += laz[x];
ma[x] += laz[x];
if(x*2+1<mn*4) {
laz[x*2]+=laz[x];
laz[x*2+1]+=laz[x];
}
laz[x]=0;
}
void eval(int x){
prop(x*2),prop(x*2+1);
mi[x]=min(mi[x*2],mi[x*2+1]);
ma[x]=max(ma[x*2],ma[x*2+1]);
}
const ll inf = 0x3f3f3f3f3f3f3f3f;
#define mid ((l+r)>>1)
void update(int x,int l,int r,int a,int b,int c){
if(l==a&&r==b)laz[x]+=c;
else {
prop(x);
if(b<=mid)update(x*2,l,mid,a,b,c);
else if(a>mid)update(x*2+1,mid+1,r,a,b,c);
else {
update(x*2,l,mid,a,mid,c);
update(x*2+1,mid+1,r,mid+1,b,c);
}
eval(x);
}
}
ll lv;
ll query(int x,int l,int r, ll c, ll cmin=inf, ll cmax=-inf) {
prop(x);
if(l==r){
cmin = min(cmin, mi[x]);
cmax = max(cmax, ma[x]);
// cerr << l << " " << cmin << " " << cmax << endl;
if(cmax-cmin<c) return lv-cmin;
else if(cmin==mi[x]) return lv-cmax+c;
else return lv-cmin;
}
else {
prop(x*2+1);
ll ncmin = min(cmin, mi[x*2+1]), ncmax = max(cmax,ma[x*2+1]);
// cerr << l << " " << r << " " << ncmin << " " << ncmax << " " << ncmax-ncmin-c << endl;
if(ncmax-ncmin<c) return query(x*2,l,mid,c,ncmin,ncmax);
else return query(x*2+1,mid+1,r,c,cmin,cmax);
}
}
struct event {
int t;
int p;
int v;
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
int q = l.size();
vector<event> es;
for(int i=0;i<q;i++){
es.push_back({i+1,l[i],v[i]});
es.push_back({i+1,r[i]+1,-v[i]});
}
sort(es.begin(), es.end(), [](event a, event b){
return a.p < b.p;
});
auto process = [&](const event&e){
update(1,0,q,e.t,q,e.v);
lv+=e.v;
};
vector<int> ret;
for(int i=0,j=0;i<n;i++){
// cerr << i << endl;
while(j<es.size() && es[j].p<=i) process(es[j++]);
ll ans = query(1,0,q,c[i]);
ret.push_back(ans);
}
return ret;
}
