#include "candies.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
int mini = 0, maxi = 0, tag = 0;
};
vector<Node> node;
const int INF = 1e15;
void applyOp(int i, int add) {
node[i].tag += add;
node[i].mini += add;
node[i].maxi += add;
}
void propage(int i) {
applyOp(i*2, node[i].tag);
applyOp(i*2+1, node[i].tag);
node[i].tag = 0;
}
pair<int, int> query(int i, int deb, int fin, int l, int r, int add) {
if(l <= deb && fin <= r) {
applyOp(i, add);
return {node[i].mini, node[i].maxi};
}
if(r <= deb || fin <= l) return {INF, -INF};
propage(i);
int mid = (deb + fin) >> 1;
auto ansL = query(i*2, deb, mid, l, r, add),
ansR = query(i*2+1, mid, fin, l, r, add);
ansL.first = min(ansL.first, ansR.first);
ansL.second = max(ansL.second, ansR.second);
node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
return ansL;
}
int getPos(int i, int deb, int fin, int mini, int maxi, int cap) {
if(fin - deb == 1) return deb;
int mid = (deb + fin) >> 1;
propage(i);
int midMin = min(mini, node[i*2+1].mini),
midMax = max(maxi, node[i*2+1].maxi);
int ans = 0;
if(midMax - midMin >= cap) ans = getPos(i*2+1, mid, fin, mini, maxi, cap);
else ans = getPos(i*2, deb, mid, midMin, midMax, cap);
node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
node[i].maxi = max(node[i*2].maxi, node[i*2+1].maxi);
return ans;
}
vector<signed> distribute_candies(vector<signed> c, vector<signed> l,
vector<signed> r, vector<signed> v) {
int n = c.size(), q = l.size();
node.resize(4*(q+1));
vector<vector<int>> req(n+1);
for(int i = 0; i < q; i++) {
req[l[i]].push_back(i);
req[r[i]+1].push_back(i);
}
vector<signed> ans(n);
for(int i = 0; i < n; i++) {
for(int id : req[i]) {
int val = v[id];
if(i == r[id]+1)
val = -v[id];
query(1, 0, q+1, id+1, q+1, val);
}
int pos = getPos(1, 0, q+1, INF, -INF, c[i]);
auto [mini, maxi] = query(1, 0, q+1, pos, q+1, 0);
auto [valPos, _0] = query(1, 0, q+1, pos, pos+1, 0);
auto [valFin, _1] = query(1, 0, q+1, q, q+1, 0);
if(mini == valPos) {
ans[i] = (signed)(valFin - maxi + c[i]);
} else {
ans[i] = (signed)(valFin - mini);
}
}
return ans;
}
