#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
int n,q;
struct node
{
long long sum;
long long min_pref,max_pref;
};
node combine(node x, node y)
{
node aux;
aux.sum = x.sum + y.sum;
aux.max_pref = max(x.max_pref, x.sum + y.max_pref);
aux.min_pref = min(x.min_pref, x.sum + y.min_pref);
return aux;
}
node aint[510000];
void upd(int nod, int st, int dr, int poz, int newv)
{
if(st==dr)
{
aint[nod] = {newv, min(0,newv), max(0,newv)};
return;
}
int mij=(st+dr)/2;
if(poz<=mij) upd(nod*2,st,mij,poz,newv);
else upd(nod*2+1,mij+1,dr,poz,newv);
aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
long long qry(int nod, int st, int dr, long long lim)
{
if(st==dr)
return max(0LL,min(aint[nod].sum,lim));
//if(aint[nod].max_pref <= lim && aint[nod].min_pref >= 0) return aint[nod].sum;
int mij=(st+dr)/2;
if(aint[nod*2+1].max_pref - aint[nod*2+1].min_pref >= lim)
return qry(nod*2+1,mij+1,dr,lim);
long long le = qry(nod*2,st,mij,lim);
if(le + aint[nod*2+1].max_pref > lim)
return lim + aint[nod*2+1].sum - aint[nod*2+1].max_pref;
if(le + aint[nod*2+1].min_pref < 0)
return 0 + aint[nod*2+1].sum - aint[nod*2+1].min_pref;
return le + aint[nod*2+1].sum;
}
vector<pair<int,int>> onpoz[200005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v)
{
n = c.size();
q = l.size();
for(int i=0;i<q;i++)
{
onpoz[l[i]].push_back({i,v[i]});
onpoz[r[i]+1].push_back({i,0});
}
vector<int> sol(n);
for(int i=0;i<n;i++)
{
for(auto [t,val]:onpoz[i])
upd(1,0,q-1,t,val);
sol[i] = qry(1,0,q-1,c[i]);
}
return sol;
}
