#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
// bruh
class ST {
private:
int n,h;
vl sa,sb,lz;
const ll STA = -1LL<<62;
const ll STB = 1LL<<62;
int log2(int v) {
if(v <= 1) return 1;
return log2(v/2)+1;
}
void ap(int p, ll val) {
sa[p] += val;
sb[p] += val;
if(p < n) {lz[p] += val;}
}
void build(int p) {
while(p > 1) {
p >>= 1;
if(p >= n) continue;
sa[p] = max(sa[p<<1],sa[p<<1|1])+lz[p];
sb[p] = min(sb[p<<1],sb[p<<1|1])+lz[p];
}
}
void psh(int p) {
for(int s=h;s>0;s--) {
int i = p>>s;
if(lz[i] != 0) {
ap(i<<1,lz[i]);
ap(i<<1|1,lz[i]);
lz[i] = 0;
}
}
}
public:
ST(int _n) {
n = _n;
h = log2(n);
sa.assign(2*n,0);
sb.assign(2*n,0);
lz.assign(n,0);
}
void up(int l, int r, ll val) {
if(l >= r) return;
l += n;r += n;
int li = l,ri = r;
for(;l<r;l>>=1,r>>=1) {
if(l&1) {ap(l++,val);
}
if(r&1) {ap(--r,val);
}
}
build(li);build(ri-1);
}
pl get(int l, int r) {
l += n;r += n;
psh(l);psh(r-1);
ll ra = STA;
ll rb = STB;
for(;l<r;l>>=1,r>>=1) {
if(l&1) {
ra = max(ra,sa[l]);
rb = min(rb,sb[l]);
l++;
}
if(r&1) {
--r;
ra = max(ra,sa[r]);
rb = min(rb,sb[r]);
}
}
return {ra,rb};
}
};
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();
l.insert(l.begin(),0);
l.insert(l.begin(),0);
r.insert(r.begin(),n-1);
r.insert(r.begin(),n-1);
v.insert(v.begin(),-(1e9+7));
v.insert(v.begin(),1e9+7);
ll q = l.size();
ST st(q);
vector<vector<pl> > ops(n+1);
for(int i=0;i<q;i++) {
ops[l[i]].emplace_back(i,v[i]);
ops[r[i]+1].emplace_back(i,-v[i]);
}
std::vector<int> ans(n);
for(int i=0;i<n;i++) {
for(const auto& op: ops[i]) {
st.up(op.first,q,op.second);
}
ll fv = st.get(q-1,q).first;
ll sv = 0,ev = q-1;
ll ls = 0;
while(sv <= ev) {
ll m = (sv+ev)/2;
pl val = st.get(m,q);
if(val.first-val.second > c[i]) {
ls = m;
sv = m+1;
} else {
ev = m-1;
}
}
pl val = st.get(ls,q);
ll los = st.get(ls,ls+1).first;
if(los == val.first) {
ans[i] = fv-val.second;
} else {
ans[i] = fv-val.first+c[i];
}
}
return ans;
}
