#include "candies.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")
const int inf = 1e9+1;
const int N = 200'010;
const int S = 2048;
int a[N], c[N];
void add(int l, int r, int x)
{
Loop (i,l,r)
a[i] = (a[i] + x > c[i]? c[i]: a[i] + x);
}
void sub(int l, int r, int x)
{
Loop (i,l,r)
a[i] = (a[i] - x < 0? 0: a[i] - x);
}
void addsub(int l, int r, int x, int y)
{
Loop (i,l,r) {
a[i] = (a[i] + x > c[i]? c[i]: a[i] + x);
a[i] = (a[i] - y < 0? 0: a[i] - y);
}
}
void subadd(int l, int r, int x, int y)
{
Loop (i,l,r) {
a[i] = (a[i] - x < 0? 0: a[i] - x);
a[i] = (a[i] + y > c[i]? c[i]: a[i] + y);
}
}
void addsubadd(int l, int r, int x, int y, int z)
{
Loop (i,l,r) {
a[i] = (a[i] + x > c[i]? c[i]: a[i] + x);
a[i] = (a[i] - y < 0? 0: a[i] - y);
a[i] = (a[i] + z > c[i]? c[i]: a[i] + z);
}
}
void subaddsub(int l, int r, int x, int y, int z)
{
Loop (i,l,r) {
a[i] = (a[i] - x < 0? 0: a[i] - x);
a[i] = (a[i] + y > c[i]? c[i]: a[i] + y);
a[i] = (a[i] - z < 0? 0: a[i] - z);
}
}
void up(int l, int r, int x)
{
if (x > 0)
add(l, r, x);
else
sub(l, r, -x);
}
void upup(int l, int r, int x, int y)
{
if (x > 0 && y > 0)
add(l, r, min(inf, x+y));
if (x <= 0 && y <= 0)
sub(l, r, min(inf, -(x+y)));
if (x > 0 && y <= 0)
addsub(l, r, x, -y);
if (x <= 0 && y > 0)
subadd(l, r, -x, y);
}
void upupup(int l, int r, int x, int y, int z)
{
if ((x > 0) == (y > 0))
return upup(l, r, clamp(-inf, x+y, inf), z);
if ((y > 0) == (z > 0))
return upup(l, r, x, clamp(-inf, y+z, inf));
if (x > 0)
addsubadd(l, r, x, -y, z);
if (x <= 0)
subaddsub(l, r, -x, y, -z);
}
void upv(int l, int r, int *a, int cnt)
{
switch (cnt) {
case 0: return;
case 1: return up(l, r, a[0]);
case 2: return upup(l, r, a[0], a[1]);
case 3: return upupup(l, r, a[0], a[1], a[2]);
}
}
std::vector<int> distribute_candies(std::vector<int> _c, std::vector<int> ql,
std::vector<int> qr, std::vector<int> qv) {
int n = _c.size();
int q = ql.size();
for (int &x : qr)
++x;
Loop (i,0,n)
c[i] = _c[i];
for (int L = 0; L < n; L += S) {
int R = min<int>(L+S, n);
for (int i = 0; i < q;) {
int cnt;
for (cnt = 0; cnt < 3 && i+cnt < q; ++cnt) {
if (!(ql[i+cnt] <= L && R <= qr[i+cnt]))
break;
}
upv(L, R, &qv[i], cnt);
i += cnt;
if (cnt != 3 && i != q) {
up(max(ql[i], L), min(qr[i], R), qv[i]);
i += 1;
}
}
}
return vector<int>(a, a+n);
}
