#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
struct N {
ll mn = 0;
ll mx = 0;
ll la = 0;
};
N it[600000];
int n, q;
int is = 1;
void tag(int i, int a) {
it[i].la += a;
it[i].mn += a;
it[i].mx += a;
}
void push(int i) {
if(it[i].la != 0) {
for(int c : {2*i, 2*i+1}) {
tag(c, it[i].la);
}
it[i].la = 0;
}
}
void pull(int i) {
it[i].mn = min(it[2*i].mn, it[2*i+1].mn);
it[i].mx = max(it[2*i].mx, it[2*i+1].mx);
}
void add(int l, int r, ll a, int i = 1, int li = 0, int ri = is) {
if(r <= li || ri <= l) return;
if(l <= li && ri <= r) {
tag(i, a);
return;
}
push(i);
int mi = (li + ri)/2;
add(l, r, a, 2*i , li, mi);
add(l, r, a, 2*i+1, mi, ri);
pull(i);
}
N qry(int l, int r, int i = 1, int li = 0, int ri = is) {
if(r <= li || ri <= l) return {(ll)1e9, (ll)-1e9, 0};
if(l <= li && ri <= r) {
return it[i];
}
push(i);
int mi = (li + ri)/2;
N ln = qry(l, r, 2*i , li, mi);
N rn = qry(l, r, 2*i+1, mi, ri);
return {min(ln.mn, rn.mn), max(ln.mx, rn.mx), 0};
}
struct Q {
int l, r, v, t;
};
// pair<ll, ll> mwalk(ll cp, ll lv, ll mn, ll mx, int i = 1, int li = 0, int ri = is) {
// ll umn = min(mn, it[i].mn);
// ll umx = min(mx, it[i].mx);
// if(umx - umn >=
// }
ll iwalk(ll cp) {
ll lv = qry(q, q+1).mx;
// cerr << lv << '\n';
int b = 0;
int e = q;
while(b != e) {
int m = (b+e)/2;
N rs = qry(m, q+1);
if(rs.mx - rs.mn >= cp) {
b = m+1;
} else {
e = m;
}
}
// cerr << "b " << b << '\n';
N at = qry(b, q+1);
if(b == 0) {
return lv - at.mn;
}
N bef = qry(b-1, q+1);
if(at.mn == bef.mn) {
return lv - at.mn;
} else {
return cp - (at.mx - lv);
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
n = c.size();
q = l.size();
while(is < q+1) is *= 2;
vector<Q> qs(q);
for(int i = 0; i < q; ++i) {
qs[i] = {l[i], r[i]+1, v[i], i};
}
vector<int> s(n);
auto swalk = [&](const auto& swalk, int b, int e, const vector<Q>& qs) -> void {
vector<Q> pass;
for(Q qr : qs) {
if(qr.l <= b && e <= qr.r) {
add(qr.t+1, q+1, qr.v);
} else if(qr.r <= b || e <= qr.l) {
continue;
} else {
pass.push_back(qr);
}
}
if(e - b == 1) {
s[b] = iwalk(c[b]);
} else {
int m = (b+e)/2;
swalk(swalk, b, m, pass);
swalk(swalk, m, e, pass);
}
for(Q qr : qs) {
if(qr.l <= b && e <= qr.r) {
add(qr.t+1, q+1, -qr.v);
}
}
};
swalk(swalk, 0, n, qs);
return s;
}
