#include "candies.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
long long lazy[1000005];
long long maxim[1000005];
int pozmax[1000005];
long long minim[1000005];
int pozmin[1000005];
long long spar[1000005];
vector<pair<int,int> >qu[200005];
long long inf=1e16;
void merge(int node,int i1,int i2)
{
if(maxim[i1]>maxim[i2])
{
maxim[node]=maxim[i1];
pozmax[node]=pozmax[i1];
}
else
{
maxim[node]=maxim[i2];
pozmax[node]=pozmax[i2];
}
if(minim[i1]<minim[i2])
{
minim[node]=minim[i1];
pozmin[node]=pozmin[i1];
}
else
{
minim[node]=minim[i2];
pozmin[node]=pozmin[i2];
}
spar[node]=spar[node*2]+spar[node*2+1];
}
void build(int node,int st,int dr)
{
if(st==dr)
{
minim[node]=0;
maxim[node]=0;
pozmin[node]=st;
pozmax[node]=st;
return;
}
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
merge(node,node*2,node*2+1);
}
void push(int node,int st,int dr)
{
minim[node]+=lazy[node];
maxim[node]+=lazy[node];
spar[node]+=lazy[node]*(dr-st+1);
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 || qst>dr || st>qdr || qst>qdr)
{
return;
}
if(qst<=st && dr<=qdr)
{
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);
merge(node,node*2,node*2+1);
}
pair<long long ,int> qmaxim(int node,int st,int dr,int qst,int qdr)
{
push(node,st,dr);
if(st>dr || qst>dr || st>qdr || qst>qdr)
{
return {-inf,-inf};
}
if(qst<=st && dr<=qdr)
{
return {maxim[node],pozmax[node]};
}
int mij=(st+dr)/2;
auto r1=qmaxim(node*2,st,mij,qst,qdr);
auto r2=qmaxim(node*2+1,mij+1,dr,qst,qdr);
if(r1.first>r2.first)
{
return r1;
}
return r2;
}
pair<long long ,int> qminim(int node,int st,int dr,int qst,int qdr)
{
push(node,st,dr);
if(st>dr || qst>dr || st>qdr || qst>qdr)
{
return {inf,inf};
}
if(qst<=st && dr<=qdr)
{
return {minim[node],pozmin[node]};
}
int mij=(st+dr)/2;
auto r1=qminim(node*2,st,mij,qst,qdr);
auto r2=qminim(node*2+1,mij+1,dr,qst,qdr);
if(r1.first<r2.first)
{
return r1;
}
return r2;
}
long long qsum(int node,int st,int dr,int qst,int qdr)
{
push(node,st,dr);
if(st>dr || qst>dr || st>qdr || qst>qdr)
{
return 0;
}
if(qst<=st && dr<=qdr)
{
return spar[node];
}
int mij=(st+dr)/2;
return qsum(node*2,st,mij,qst,qdr)+qsum(node*2+1,mij+1,dr,qst,qdr);
}
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();
for(int i=1;i<=q;i++)
{
qu[l[i-1]].push_back({i,v[i-1]});
qu[r[i-1]+1].push_back({i,-v[i-1]});
}
build(1,0,q);
//cin>>lim;
vector<int>s;
long long sumtot=0;
for(int i=0;i<n;i++)
{
for(auto j:qu[i])
{
update(1,0,q,j.first,q,j.second);
sumtot+=j.second;
}
int st=0,dr=q;
while(st<=dr)
{
int mij=(st+dr)/2;
pair<long long,int> maxq=qmaxim(1,0,q,mij,q);
pair<long long,int> minq=qminim(1,0,q,mij,q);
if(maxq.first-minq.first>=c[i])
{
st=mij+1;
}
else
{
dr=mij-1;
}
}
if(dr==-1)
{
// cout<<spar[n]<<" ";
pair<long long,int> minq=qminim(1,0,q,0,q);
s.push_back(sumtot-minq.first);
}
else
{
pair<long long,int> minq=qminim(1,0,q,dr,q);
if(minq.second==dr)
{
pair<long long,int> maxq=qmaxim(1,0,q,dr,q);
//cout<<c[i]-(spar[pozmax[dr-1]]-spar[n])<<" ";
s.push_back(c[i]-(maxq.first-sumtot));
}
else
{
//cout<<spar[n]-spar[pozmin[dr-1]]<<" ";
s.push_back(sumtot-minq.first);
}
}
}
return s;
}
