#include<bits/stdc++.h>
#include"candies.h"
using namespace std;
using ll = long long;
struct segtree {
struct node {
ll s{}, mx{}, mn{};
node operator+(const node& o) {
return node{s + o.s, max(o.mx, o.s + mx), min(o.mn, o.s + mn)};
}
};
int n;
vector<node> t;
segtree(int m) : n(m), t(m*4) {}
void upd(int i, int x) {
t[i += n] = node {x, max(0, x), min(0, x)};
for (i /= 2; i >= 1; i /= 2)
t[i] = t[i*2] + t[i*2+1];
}
node query(int l, int r) {
node resl, resr;
l += n; r += n;
while (l <=r) {
if (l%2==1) resl = resl + t[l++];
if (r%2==0) resr = t[r--] + resr;
l /= 2; r /= 2;
}
return resl + resr;
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size();
int m = (int)v.size();
vector<vector<int>> in(n), out(n);
for (int i = 0; i < m; i++) {
in[l[i]].push_back(i);
out[r[i]].push_back(i);
}
segtree vcur(m);
for(int i = 0; i < n; i ++){
for (int j : in[i]) {
vcur.upd(j, -v[j]);
}
int l = 0, r = m;
while(l <= r){
int mid = (l + r) >> 1;
auto [s, mx, mn] = vcur.query(mid, m-1);
if(mx - mn >= c[i]) {
l = mid + 1;
}else r = mid - 1;
}
r ++;
if(r == 0 || v[r - 1] < 0){
auto [s, mx, mn] = vcur.query(r, m-1);
c[i] = -mn;
}else{
auto [s, mx, mn] = vcur.query(r, m-1);
c[i] = c[i] - mx;
}
for (int j : out[i]) {
vcur.upd(j, 0);
}
}
//for(auto u : suf) cout << u << ' ';cout << endl;
return c;
}
