#include "candies.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>
int cap[200005];
int val[200005];
long long valmax;
long long maxim[800005];
long long minim[800005];
long long lazy[800005];
using namespace std;
void push(int node,int st,int dr)
{
maxim[node]+=lazy[node];
minim[node]+=lazy[node];
if(st!=dr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void update(int node,int st,int dr,int qst,int qdr,int val)
{
push(node,st,dr);
if(st>dr || st>qdr|| qst>dr || qst>qdr)
{
return;
}
if(qst<=st && dr<=qdr)
{
if(maxim[node]==minim[node])
{
int diff=maxim[node];
int newval=max(0ll,min(maxim[node]+val,valmax));
diff=newval-maxim[node];
lazy[node]=diff;
push(node,st,dr);
return;
}
if(val+maxim[node]<=valmax && val+minim[node]>=0)
{
lazy[node]=val;
push(node,st,dr);
return;
}
}
int mij=(st+dr)/2;
update(node*2,st,mij,qst,qdr,val);
update(node*2+1,mij+1,dr,qst,qdr,val);
maxim[node]=max(maxim[node*2],maxim[node*2+1]);
minim[node]=min(minim[node*2],minim[node*2+1]);
}
vector<int>rasp;
void dfs(int node,int st,int dr)
{
push(node,st,dr);
if(st==dr)
{
rasp.push_back(minim[node]);
return;
}
int mij=(st+dr)/2;
dfs(node*2,st,mij);
dfs(node*2+1,mij+1,dr);
}
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();
valmax=c[0];
for(int i=0;i<l.size();i++)
{
update(1,1,n,l[i]+1,r[i]+1,v[i]);
}
dfs(1,1,n);
return rasp;
}
