#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int const MAX=200005;
ll const INF=1e18;
struct node{
ll mn,mx,lazy;
};
struct segment_tree{
node v[4*MAX];
void propagate(int nod){
if(v[nod].lazy){
int lz=v[nod].lazy;
v[2*nod].mn+=lz;
v[2*nod].mx+=lz;
v[2*nod].lazy+=lz;
v[2*nod+1].mn+=lz;
v[2*nod+1].mx+=lz;
v[2*nod+1].lazy+=lz;
v[nod].lazy=0;
}
}
void combine(int nod){
v[nod].mn=min(v[2*nod].mn,v[2*nod+1].mn);
v[nod].mx=max(v[2*nod].mx,v[2*nod+1].mx);
}
void update(int nod,int st,int dr,int a,int b,int del){
if(a<=st && dr<=b){
v[nod].mn+=del;
v[nod].mx+=del;
v[nod].lazy+=del;
}
else{
propagate(nod);
int mij=(st+dr)/2;
if(a<=mij)
update(2*nod,st,mij,a,b,del);
if(mij<b)
update(2*nod+1,mij+1,dr,a,b,del);
combine(nod);
}
}
ll query(int nod,int st,int dr,int poz){
if(st==dr)
return v[nod].mn;
propagate(nod);
int mij=(st+dr)/2;
if(poz<=mij)
return query(2*nod,st,mij,poz);
else
return query(2*nod+1,mij+1,dr,poz);
}
int bin_search(int nod,int st,int dr,int lim,ll& mn,ll& mx){
if(st==dr){
mn=min(mn,v[nod].mn);
mx=max(mx,v[nod].mx);
return st;
}
propagate(nod);
int mij=(st+dr)/2;
if(max(mx,v[2*nod+1].mx)-min(mn,v[2*nod+1].mn)>lim)
return bin_search(2*nod+1,mij+1,dr,lim,mn,mx);
else{
mn=min(mn,v[2*nod+1].mn);
mx=max(mx,v[2*nod+1].mx);
return bin_search(2*nod,st,mij,lim,mn,mx);
}
}
}aint;
vector<int>adauga[MAX];
vector<int>sterge[MAX];
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
int n=c.size();
int q=v.size();
int i;
for(i=0;i<q;++i){
adauga[l[i]].push_back(i+1);
sterge[r[i]+1].push_back(i+1);
}
vector<int>ans(n);
for(i=0;i<n;++i){
for(auto qr : adauga[i])
aint.update(1,0,q,qr,q,v[qr-1]);
for(auto qr : sterge[i])
aint.update(1,0,q,qr,q,-v[qr-1]);
if(aint.v[1].mx-aint.v[1].mn<=c[i])
ans[i]=aint.query(1,0,q,q)-aint.v[1].mn;
else{
ll mn=INF,mx=-INF;
int poz=aint.bin_search(1,0,q,c[i],mn,mx);
if(mn==aint.query(1,0,q,poz))
ans[i]=aint.query(1,0,q,q)-mx+c[i];
else
ans[i]=aint.query(1,0,q,q)-mn;
}
}
return ans;
}
