#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int n;
struct A {
ll mn, mx;
A() {
mn = mx = 0ll;
}
A operator + (const A& o) const {
A t;
t.mn = min(mn, o.mn);
t.mx = max(mx, o.mx);
return t;
}
} tree[4 * N], _T;
ll lazy[4 * N];
void lzy(int now, int l, int r) {
if (!lazy[now]) return;
tree[now].mn += lazy[now];
tree[now].mx += lazy[now];
if (l != r) {
lazy[2 * now] += lazy[now];
lazy[2 * now + 1] += lazy[now];
}
lazy[now] = 0;
}
void update(int ql, int qr, ll w, int now = 1, int l = 0, int r = n) {
lzy(now, l, r);
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
lazy[now] += w;
lzy(now, l, r);
return;
}
int mid = (l + r) / 2;
update(ql, qr, w, 2 * now, l, mid);
update(ql, qr, w, 2 * now + 1, mid + 1, r);
tree[now] = tree[2 * now] + tree[2 * now + 1];
}
A query(int ql, int qr, int now = 1, int l = 0, int r = n) {
lzy(now, l, r);
if (ql <= l && r <= qr) return tree[now];
int mid = (l + r) / 2;
if (qr <= mid) return query(ql, qr, 2 * now, l, mid);
if (ql > mid) return query(ql, qr, 2 * now + 1, mid + 1, r);
return query(ql, qr, 2 * now, l, mid) + query(ql, qr, 2 * now + 1, mid + 1, r);
}
vector<pair<int, int>> q[N];
vector<int> distribute_candies(vector<int> c, vector<int> _l, vector<int> _r, vector<int> _v) {
n = _l.size();
int m = c.size();
vector<int> ans(m);
for (int i = 0;i < n;i++) {
q[_l[i]].push_back({ _v[i], i + 1 });
q[_r[i] + 1].push_back({ -_v[i], i + 1 });
}
// find last point that mx - mn <= c[i]
ll sum = 0;
for (int i = 0;i < m;i++) {
for (auto& x : q[i]) {
update(x.second, n, x.first);
sum += x.first;
}
int l = 0, r = n;
while (l < r) {
int mid = (l + r) / 2;
A now = query(mid, n);
if (now.mx - now.mn <= c[i]) r = mid;
else l = mid + 1;
}
if (l == 0) {
ans[i] = sum - query(0, n).mn;
continue;
}
A now = query(l, n);
ll prev = query(l - 1, l - 1).mn;
if (prev < now.mn) {
ans[i] = sum - (now.mx - c[i]);
}
else {
ans[i] = sum - now.mn;
}
}
return ans;
}
