#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
// domain [l, r] -> [l + d, r + d] is linear
ll l, r, d;
ll operator()(ll x)
{
if (x < l)
return l + d;
if (x <= r)
return x + d;
return r + d;
}
} seg[800005];
node merge(node p, node q)
{
auto [l, r, d] = p;
auto [x, y, _] = q;
// merge domain
l += d, r += d;
l = max(l, x);
r = min(r, y);
if (l > r)
l = r = d;
l -= d, r -= d;
// compute d
d = q(p(l)) - l;
return node{l, r, d};
}
int n, q;
node emp;
void init()
{
for (int i = 1; i <= 4 * n; i++)
seg[i] = emp;
}
void modify(int pos, node val, int i = 1, int L = 0, int R = q - 1)
{
if (L == R)
seg[i] = val;
else
{
int mid = (L + R) / 2;
if (pos <= mid)
modify(pos, val, i << 1, L, mid);
else
modify(pos, val, i << 1 | 1, mid + 1, R);
seg[i] = merge(seg[i << 1], seg[i << 1 | 1]);
}
}
vector<int> in[200000], out[200001];
node base[200000];
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v)
{
vector<int> ans;
n = c.size(), q = l.size();
int C = c[0];
emp = {0, C, 0};
for (int i = 0; i < q; i++)
{
in[l[i]].emplace_back(i);
out[r[i] + 1].emplace_back(i);
base[i] = emp;
if (v[i] < 0)
{
v[i] = max(-C, v[i]);
base[i] = node{-v[i], C, v[i]};
}
else
{
v[i] = min(C, v[i]);
base[i] = node{0, C - v[i], v[i]};
}
}
init();
for (int i = 0; i < n; i++)
{
for (auto j : in[i])
modify(j, base[j]);
for (auto j : out[i])
modify(j, emp);
ans.emplace_back(seg[1](0));
}
return ans;
}
