#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct ST
{
int l, r;
int lazy = 0;
ST *left, *right;
int mn1;
int mn2;
ST(int l, int r, const vector<int>&c): l(l), r(r)
{
if (l < r)
{
left = new ST(l, (l + r) / 2, c);
right = new ST((l + r) / 2 + 1, r, c);
mn1 = min(left->mn1, right->mn1);
mn2 = min(left->mn2, right->mn2);
}
else
{
mn1 = 0;
mn2 = c[l];
}
}
void fix()
{
mn1 += lazy;
mn2 -= lazy;
if (lazy != 0 && l < r)
{
left->lazy += lazy;
right->lazy += lazy;
}
lazy = 0;
}
void upd(int x, int y, int del)
{
fix();
if (x <= l && r <= y)
{
if (del > 0)
{
if (mn2 >= del)
{
lazy += del;
return fix();
}
else
{
left->upd(x, y, del);
right->upd(x, y, del);
mn1 = min(left->mn1, right->mn1);
mn2 = min(left->mn2, right->mn2);
}
}
if (del < 0)
{
if (mn1 >= -del)
{
lazy += del;
return fix();
}
else
{
left->upd(x, y, del);
right->upd(x, y, del);
mn1 = min(left->mn1, right->mn1);
mn2 = min(left->mn2, right->mn2);
}
}
}
else if (r < x || y < l)
return;
else
{
left->upd(x, y, del);
right->upd(x, y, del);
mn1 = min(left->mn1, right->mn1);
mn2 = min(left->mn2, right->mn2);
}
}
void get(vector<int>&c)
{
fix();
if (l < r)
{
left->get(c);
right->get(c);
}
else
c[l] = mn1;
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size();
ST med(0, n - 1, c);
for (int i = 0; i < l.size(); i++)
{
med.upd(l[i], r[i], v[i]);
}
med.get(c);
return c;
}
