#include "candies.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 2e5 + 5;
int n, q;
long long lazy[N * 4], vmin[N * 4], vmax[N * 4];
long long minF, maxF;
vector<int> Q[N];
void down(int range, int pos) {
if (lazy[pos]) {
vmin[pos] += lazy[pos];
vmax[pos] += lazy[pos];
if (range) {
lazy[pos * 2] += lazy[pos];
lazy[pos * 2 + 1] += lazy[pos];
}
lazy[pos] = 0;
}
}
void update(int x, int y, int val, int l = 0, int r = q, int pos = 1) {
if (x > r || y < l || x > y) return;
if (x <= l && r <= y) {
lazy[pos] += val;
return;
}
down(r - l, pos);
int mid = (l + r) / 2;
update(x, y, val, l, mid, pos * 2);
update(x, y, val, mid + 1, r, pos * 2 + 1);
vmin[pos] = min(vmin[pos * 2] + lazy[pos * 2], vmin[pos * 2 + 1] + lazy[pos * 2 + 1]);
vmax[pos] = max(vmax[pos * 2] + lazy[pos * 2], vmax[pos * 2 + 1] + lazy[pos * 2 + 1]);
}
int query(int diff, int l = 0, int r = q, int pos = 1) {
down(r - l, pos);
if (max(maxF, vmax[pos]) - min(minF, vmin[pos]) < diff) {
maxF = max(maxF, vmax[pos]);
minF = min(minF, vmin[pos]);
return l - 1;
}
if (l == r) {
maxF = max(maxF, vmax[pos]);
minF = min(minF, vmin[pos]);
if (maxF == vmax[pos]) maxF = minF + diff;
else minF = maxF - diff;
return l;
}
int mid = (l + r) / 2;
int tmp = query(diff, mid + 1, r, pos * 2 + 1);
if (tmp > mid) return tmp;
return query(diff, l, mid, pos * 2);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
n = c.size();
q = v.size();
vector<int> ans(n, 0);
REP(i, 0, q) {
Q[l[i]].push_back(i);
Q[r[i] + 1].push_back(i + q);
}
REP(i, 0, n) {
for(int id : Q[i]) {
if (id < q) update(0, id, v[id]);
else update(0, id - q, -v[id - q]);
}
minF = maxF = 0;
int tmp = query(c[i]);
ans[i] = maxF;
}
return ans;
}
