#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a.begin(), a.end())
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define int long long
struct node{
node* l;
node* r;
int mx,mn,lazy=0;
void update(){
if(l!=NULL) { mn=min(mn,l->mn); mx=max(mx,l->mx); }
if(r!=NULL) { mn=min(mn,r->mn); mx=max(mx,r->mx); }
}
};
struct segtree{
int n;
node* root;
void propagate(node* x){
if(x->l!=NULL) {
x->l->lazy+=x->lazy;
x->l->mn+=x->lazy;
x->l->mx+=x->lazy;
}
if(x->r!=NULL) {
x->r->lazy+=x->lazy;
x->r->mn+=x->lazy;
x->r->mx+=x->lazy;
}
x->lazy=0;
}
void build(node* x, int l, int r){
if(l==r) return;
x->l=new node{NULL,NULL,0,0,0};
x->r=new node{NULL,NULL,0,0,0};
int mid=(l+r)/2;
build(x->l,l,mid);
build(x->r,mid+1,r);
}
void update(node* x, int l, int r, int qL, int qR, int v){
if(r<qL||l>qR) return;
if(l>=qL&&r<=qR){
x->mx+=v;
x->mn+=v;
x->lazy+=v;
return;
}
propagate(x);
int mid=(l+r)/2;
update(x->l,l,mid,qL,qR,v);
update(x->r,mid+1,r,qL,qR,v);
x->update();
}
pair<int,int> query(node* x, int l, int r, int qL, int qR){
if(r<qL||l>qR) return {1e9,-1e9};
if(l>=qL&&r<=qR) return {x->mn,x->mx};
propagate(x);
int mid=(l+r)/2;
pair<int,int> u1=query(x->l,l,mid,qL,qR);
pair<int,int> u2=query(x->r,mid+1,r,qL,qR);
return {min(u1.first,u2.first),max(u1.second,u2.second)};
}
segtree(int _n){
n=_n;
root=new node{NULL,NULL,0,0,0};
build(root, 0, n-1);
}
void update(int l, int r, int v){
update(root,0,n-1,l,r,v);
return;
}
pair<int,int> query(int l, int r){
return query(root,0,n-1,l,r);
}
};
std::vector<signed> distribute_candies(std::vector<signed> _c, std::vector<signed> l, std::vector<signed> r, std::vector<signed> v) {
int n = _c.size();
vector<signed> s(n);
int q=sz(l);
segtree seg(q);
int j=0;
vector<pair<int,int>> sc(n);
for (int i = 0; i < n; i++) sc[i]={_c[i],i};
sort(rall(sc));
for (int i = 0; i < q; i++) seg.update(i,q-1,v[i]);
for (int i = 0; i < n; i++)
{
int c=sc[i].first;
pair<int,int> qe=seg.query(j,q-1);
while(qe.first<0||qe.second>c){
int vl=-1;
int l=j;
int r=q-1;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
pair<int,int> qr=seg.query(j,mid);
if(qr.first<0||qr.second>c){
ans=mid;
if(qr.first<0) vl=qr.first;
else if(qr.second>c) vl=qr.second;
r=mid-1;
}else{
l=mid+1;
}
}
j=ans;
if(vl<0) seg.update(ans,q-1,-vl);
else seg.update(ans,q-1,c-vl);
qe=seg.query(j,q-1);
}
s[sc[i].second]=seg.query(q-1,q-1).first;
}
return s;
}
