#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#include "candies.h"
using namespace std;
const int N = 2e5 + 5;
long long lazy[4 * N];
struct node {
long long mx, mn, id1, id2, sum;
} tree[4 * N], Z;
node merge(node a, node b) {
node c = {0,0,0,0, 0};
if(a.mx > b.mx) c.mx = a.mx, c.id1 = a.id1;
else c.mx = b.mx, c.id1 = b.id1;
if(a.mn < b.mn) c.mn = a.mn, c.id2 = a.id2;
else c.mn = b.mn, c.id2 = b.id2;
c.sum = 0;
return c;
}
void build(int u,int l,int r) {
if(l == r) {
tree[u].id1 = tree[u].id2 = l;
return;
}
int mid = (l + r)/2;
build(2 * u, l, mid); build(2 * u + 1,mid + 1,r);
tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
void push(int u,int l,int r) {
tree[u].mx += lazy[u];
tree[u].mn += lazy[u];
tree[u].sum += lazy[u];
if(l != r) {
lazy[2 * u] += lazy[u]; lazy[2 * u + 1] += lazy[u];
}
lazy[u] = 0;
}
void upd(int u,int st, int en,int l,int r,long long val) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lazy[u] = val;
push(u, l, r);
return;
}
int mid = (l + r)/2;
upd(2 * u,st,en,l,mid,val); upd(2 * u + 1,st,en,mid + 1,r,val);
tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
node get(int u, int st, int en,int l,int r) {
push(u,l,r);
if(l > en || r < st) return Z;
if(st <= l && r <= en) return tree[u];
int mid = (l + r)/2;
return merge(get(2 * u,st,en,l,mid), get(2 * u + 1,st,en,mid + 1,r));
}
vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size(), q = r.size();
vector<int> s(n); Z.mn = 1e15; Z.mx = -1e15;
vector<vector<pii> > st(n + 1), en(n + 1);
for(int i = 0; i < r.size(); i++) {
st[l[i]].push_back({i + 1, v[i]});
en[r[i] + 1].push_back({i + 1, -v[i]});
}
build(1,0,q);
for(int i = 0; i < n; i++) {
for(int j = 0; j < en[i].size(); j++) {
upd(1, en[i][j].f, q, 0, q, en[i][j].s);
}
for(int j = 0; j < st[i].size(); j++) {
upd(1,st[i][j].f, q, 0, q, st[i][j].s);
}
int last = 0;
{
int l = 1, r = q;
while(l <= r) {
int mid = (l + r)/2;
node g = get(1, mid - 1, q, 0, q);
if(g.mx - g.mn >= c[i]) {
l = mid + 1;
last = mid;
} else r = mid - 1;
}
}
long long sum = 0, mn = 0;
for(int j = last; j < q; j++) {
if(l[j] <= i && i <= r[j]) {
sum += v[j];
mn = min(mn, sum);
}
}
node g = get(1, last - 1, q, 0, q);
if(last == 0) s[i] = get(1, q, q, 0, q).mx - get(1, last, last, 0, q).mx,
s[i] -= get(1, last + 1, q, 1, q).mn - get(1, 1, last, 1, q).sum;
else if(g.id1 > g.id2) {
s[i] = c[i] + get(1, q, q, 0, q).mx - get(1, g.id1, g.id1, 0, q).mx;
}
else {
s[i] = get(1, q, q, 0, q).mx - get(1, g.id2, g.id2, 0, q).mx;
}
}
return s;
}
