#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node {
long long sum = 0, min_pref = 0, max_pref = 0;
};
node combine(node lx, node rx) {
node ret;
ret.sum = lx.sum + rx.sum;
ret.min_pref = min(lx.min_pref, lx.sum + rx.min_pref);
ret.max_pref = max(lx.max_pref, lx.sum + rx.max_pref);
return ret;
}
node seg[N * 2];
void upd(int nd, int l, int r, int p, int v) {
if (l == r) {
seg[nd].sum = v;
seg[nd].min_pref = min(0, v);
seg[nd].max_pref = max(0, v);
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p, v);
} else {
upd(rs, mid + 1, r, p, v);
}
seg[nd] = combine(seg[nd + 1], seg[rs]);
}
int qry(int nd, int l, int r, int c) {
if (l == r) {
return max(0LL, min((long long) c, seg[nd].sum));
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (seg[rs].max_pref - seg[rs].min_pref >= c) {
return qry(rs, mid + 1, r, c);
}
int ret = qry(nd + 1, l, mid, c);
if (ret + seg[rs].min_pref <= 0) {
ret = seg[rs].sum - seg[rs].min_pref;
} else if (ret + seg[rs].max_pref >= c) {
ret = c + (seg[rs].sum - seg[rs].max_pref);
} else {
ret += seg[rs].sum;
}
return ret;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = (int) c.size();
int q = (int) l.size();
vector<vector<int>> open(n);
vector<vector<int>> close(n);
for (int i = 0; i < q; ++i) {
open[l[i]].push_back(i);
close[r[i]].push_back(i);
}
vector<int> s(n);
for (int i = 0; i < n; ++i) {
for (int qi : open[i]) {
upd(0, 0, q - 1, qi, v[qi]);
}
s[i] = qry(0, 0, q - 1, c[i]);
for (int qi : close[i]) {
upd(0, 0, q - 1, qi, 0);
}
}
return s;
}
