#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{ //range sum updates, range max and min queries
int s,e,m;
ll mn=0,mx=0,lazy=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void propo(){
if (lazy){
mn+=lazy;
mx+=lazy;
if (s!=e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
}
void update(int i,int j,ll k){
if (s==i && e==j) lazy+=k;
else{
if (j<=m) l->update(i,j,k);
else if (m<i) r->update(i,j,k);
else l->update(i,m,k),r->update(m+1,j,k);
l->propo(),r->propo();
mn=min(l->mn,r->mn);
mx=max(l->mx,r->mx);
}
}
ll query_mn(int i,int j){
propo();
if (s==i && e==j) return mn;
else if (j<=m) return l->query_mn(i,j);
else if (m<i) return r->query_mn(i,j);
else return min(l->query_mn(i,m),r->query_mn(m+1,j));
}
ll query_mx(int i,int j){
propo();
if (s==i && e==j) return mx;
else if (j<=m) return l->query_mx(i,j);
else if (m<i) return r->query_mx(i,j);
else return max(l->query_mx(i,m),r->query_mx(m+1,j));
}
} *root=new node(0,200005);
struct upd{
int pos;
int ct;
ll val;
};
int n,q;
int cap[200005];
vector<upd> u;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n=sz(c),q=sz(l);
rep(x,0,n) cap[x]=c[x];
rep(x,0,q){
u.pub(upd({l[x],x+2,v[x]}));
u.pub(upd({r[x]+1,x+2,-v[x]}));
}
sort(all(u),[](upd i,upd j){
return i.pos>j.pos;
});
root->update(0,0,1e18);
vector<int> ans;
rep(x,0,n){
while (!u.empty() && u.back().pos==x){
root->update(u.back().ct,200005,u.back().val);
u.pob();
}
//cout<<x<<": "; rep(x,0,5) cout<<root->query_mn(x,x)<<" "; cout<<endl;
//cout<<"cap: "<<cap[x]<<endl;
int lo=0,hi=200005,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (root->query_mx(mi,200005)-root->query_mn(mi,200005)>cap[x]) lo=mi;
else hi=mi;
}
//cout<<lo<<" "<<hi<<endl;
if (root->query_mn(lo,lo)==root->query_mn(lo,200005)){
//cout<<"hit max"<<endl;
ans.pub(cap[x]-(root->query_mx(hi,200005)-root->query_mx(200005,200005)));
}
else{
//cout<<"hit min"<<endl;
ans.pub(root->query_mn(200005,200005)-root->query_mn(hi,200005));
}
}
return ans;
}
