#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define pill pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;
const ll N = 3e5;
ll n, m;
struct seg {
ll mx[4 * N] = {0};
ll mn[4 * N] = {0};
ll p[4 * N] = {0};
void push(ll v, ll tl, ll tr) {
mx[v] += p[v];
mn[v] += p[v];
if(tl != tr) {
p[v * 2] += p[v];
p[v * 2 + 1] += p[v];
}
p[v] = 0;
}
void build(ll v = 1, ll tl = 0, ll tr = m) {
mx[v] = mn[v] = 0;
p[v] = 0;
if(tl == tr) {
return;
}
ll m = (tl + tr) >> 1ll;
build(v * 2, tl, m);
build(v * 2 + 1, m + 1, tr);
}
void upd(ll l, ll r, ll z, ll v = 1, ll tl = 0, ll tr = m) {
push(v, tl, tr);
if(l > tr || tl > r)return;
if(l <= tl && tr <= r) {
p[v] += z;
push(v, tl, tr);
return;
}
ll m = (tl + tr) >> 1ll;
upd(l, r, z, v * 2, tl, m);
upd(l, r, z, v * 2 + 1, m + 1, tr);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
pill get(ll l, ll r, ll v = 1, ll tl = 0, ll tr = m) {
push(v, tl, tr);
if(l > tr || tl > r)return mp(1e17, -1e17);
if(l <= tl && tr <= r)return mp(mn[v], mx[v]);
ll m = (tl + tr) >> 1ll;
pill a = get(l, r, v * 2, tl, m);
pill b = get(l, r, v * 2 + 1, m + 1, tr);
return mp(min(a.f, b.f), max(a.s, b.s));
}
} rt;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size();
m = l.size();
rt.build();
vector<int> s(n);
vector<int> scan[n + 2];
for(int i = 0; i < l.size(); i++) {
scan[l[i]].pb(i);
scan[r[i] + 1].pb(i);
}
for(int i = 0; i < n; i++) {
for(auto u : scan[i]) {
if(r[u] + 1 == i) {
rt.upd(u + 1, m, -v[u]);
} else {
rt.upd(u + 1, m, v[u]);
}
}
ll L = 0, R = m, ans = -1;
while(L <= R) {
ll M = (L + R) >> 1ll;
pill z = rt.get(M, m);
if(z.s - z.f >= c[i]) {
ans = M;
L = M + 1;
} else {
R = M - 1;
}
}
ll zn = rt.get(m, m).f;
if(ans == -1) {
s[i] = zn;
continue;
} else {
pill z = rt.get(ans + 1, m);
pill z2 = rt.get(ans, m);
if(z2.s == z.s) {
s[i] = c[i] - (z.s - zn);
} else {
s[i] = (zn - z.f);
}
}
}
return s;
}
