#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int, int>
#define pll pair<ll,ll>
#include <vector>
/*
3
10 15 13
2
0 2 20
0 1 -11
*/
using namespace std;
const int nmax = 200001;
struct node{
ll sum, mn, mx;
int mni, mxi;
node(){
sum = 0;
mn = 1e18;
mx = -1e18;
}
}t[4 * nmax];
node merg(node a, node b){
node c;
c.sum = a.sum + b.sum;
if(a.mn < a.sum + b.mn){
c.mn = a.mn, c.mni = a.mni;
}
else c.mn = a.sum + b.mn, c.mni = b.mni;
if(a.mx > a.sum + b.mx){
c.mx = a.mx, c.mxi = a.mxi;
}
else c.mx = a.sum + b.mx, c.mxi = b.mxi;
return c;
}
node get(int v, int l, int r, int st, int fin){
if(l > fin || r < st){
return {};
}
if(l >= st && r <= fin){
return t[v];
}
int m = (l + r) / 2;
return merg(get(2 * v ,l, m, st, fin),
get(2 * v + 1, m + 1, r, st, fin));
}
void update(int v, int l, int r, int pos, ll val){
if(l > pos || r < pos)
return;
if(l == r){
t[v].mn = t[v].mx = t[v].sum = val;
t[v].mni = t[v].mxi = l;
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v + 1, m + 1, r, pos, val);
t[v] = merg(t[2 * v], t[2 * v + 1]);
}
ll getsum(int v, int l, int r, int st, int fin){
if(l > fin || r < st)
return 0;
if(l >= st && r <= fin)
return t[v].sum;
int m = (l + r) / 2;
return getsum(2 * v, l, m, st, fin) + getsum(2 * v + 1, m + 1, r, st, fin);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
vector <int> ans(n);
int m = l.size();
update(1, 1, m + 2, 1, 1e18);
update(1, 1, m + 2, 2, -1e18);
vector <vector <pii> > in(n + 1);
for(int i = 0; i < m; i++){
in[l[i]].pb({v[i], i + 3});
in[r[i] + 1].pb({0, i + 3});
}
for(int i = 0; i < n; i++){
for(auto to : in[i]){
update(1, 1, m + 2, to.s, to.f);
}
int l = 0, r = m + 3;
while(l + 1 < r){
int mid = (l + r) / 2;
node x = get(1, 1, m + 2, mid, m + 2);
if(x.mx - x.mn >= c[i]) l = mid;
else r = mid;
}
//cout << l << "\n";
node x = get(1, 1, m + 2, l, m + 2);
if(x.mni < x.mxi){
ans[i] = c[i] - getsum(1, 1, m + 2, 1, l - 1) - x.mx + t[1].sum;
}
else ans[i] = t[1].sum - getsum(1, 1, m + 2, 1, l - 1) - x.mn;
}
return ans;
}
