#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
const int N=2e5+10;
ll dif[N];
struct Data
{
int mx[3]={0},mi[3]={0};
ll lzy[3]={0};
} seg[N<<2];
Data merge(Data a,Data b)
{
Data res;
for(int j=0;j<3;j++)
{
res.mx[j]=max(a.mx[j],b.mx[j]);
res.mi[j]=min(a.mi[j],b.mi[j]);
}
return res;
}
Data SeT(int c)
{
int h=c,f=0;
Data res;
res.mi[0]=res.mx[0]=h-f;
res.mi[1]=res.mx[1]=h-c-f;
res.mi[2]=res.mx[2]=c;
return res;
}
void push(int v,int l,int r) // c never changes
{
int lc=v<<1,rc=lc|1;
if(seg[v].lzy[0])
{
seg[v].mi[0]=seg[v].mx[0]=0;
seg[v].mi[1]=-seg[v].mx[2];
seg[v].mx[1]=-seg[v].mi[2];
if(l!=r)
{
seg[lc].lzy[0]=seg[lc].lzy[1]=seg[lc].lzy[2]=0;
seg[rc].lzy[0]=seg[rc].lzy[1]=seg[rc].lzy[2]=0;
seg[lc].lzy[0]=seg[rc].lzy[0]=1;
}
seg[v].lzy[0]=0;
}
if(seg[v].lzy[1])
{
seg[v].mi[1]=seg[v].mx[1]=0;
seg[v].mi[0]=seg[v].mi[2];
seg[v].mx[0]=seg[v].mx[2];
if(l!=r)
{
seg[lc].lzy[0]=seg[lc].lzy[1]=seg[lc].lzy[2]=0;
seg[rc].lzy[0]=seg[rc].lzy[1]=seg[rc].lzy[2]=0;
seg[lc].lzy[1]=seg[rc].lzy[1]=1;
}
seg[v].lzy[1]=0;
}
if(seg[v].lzy[2])
{
seg[v].mi[0]-=seg[v].lzy[2];
seg[v].mx[0]-=seg[v].lzy[2];
seg[v].mi[1]-=seg[v].lzy[2];
seg[v].mx[1]-=seg[v].lzy[2];
if(l!=r)
{
seg[lc].lzy[2]+=seg[v].lzy[2];
seg[rc].lzy[2]+=seg[v].lzy[2];
}
seg[v].lzy[2]=0;
}
}
void Build(vector<int>&c ,int l=1,int r=n,int v=1)
{
if(l==r)
{
seg[v]=SeT(c[l-1]);
return;
}
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
Build(c,l,m,lc);
Build(c,m+1,r,rc);
seg[v]=merge(seg[lc],seg[rc]);
}
void Update(int ql,int qr,int qv,int l=1,int r=n,int v=1)
{
push(v,l,r); // causing all lzy to become zero
if(qr<l or r<ql)return;
if(ql<=l and r<=qr and seg[v].mx[0]<=qv) // all moving to right border
{
seg[v].lzy[0]=1;
// we need to set the seg[v].mx[0]=0
push(v,l,r);
return;
}
if(ql<=l and r<=qr and qv<=seg[v].mi[1]) // all moving to right border
{
seg[v].lzy[1]=1;
push(v,l,r);
// we need to set the seg[v].mi[1]=0
return;
}
if(ql<=l and r<=qr and seg[v].mx[1]<=qv and qv<=seg[v].mi[0]) // all moving to right border
{
seg[v].lzy[2]+=qv;
push(v,l,r);
// we need to set the seg[v].mi[1]=0
return;
}
//qv<=seg[v].mi[1]
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
Update(ql,qr,qv,l,m,lc);
Update(ql,qr,qv,m+1,r,rc);
seg[v]=merge(seg[lc],seg[rc]);
}
int GeT(int i,int l=1,int r=n,int v=1)
{
push(v,l,r);
if(l==r)
{
return seg[v].mx[1];
}
int m=(l+r)>>1;
if(i<=m)
return GeT(i,l,m,v<<1);
return GeT(i,m+1,r,2*v+1);
}
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();
// Build(c);
for(int i=0;i<q;i++)
{
l[i]++;
r[i]++;
dif[l[i]]+=v[i];
dif[r[i]+1]-=v[i];
// Update(l[i],r[i],v[i]);
}
vector<int> fnl;
for(int i=1;i<=n;i++)
{
dif[i]+=dif[i-1];
// int x=GeT(i);
fnl.push_back(min(dif[i],(ll)c[i-1]));
}
return fnl;
}
