#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f1 first
#define s2 second
using ii = pair<int, int>;
using ll = long long;
using pl = pair<ll, ll>;
const int MAX = 2e5 + 69;
const ll inf = (ll)1e18 + 69;
struct Segtree
{
struct Node
{
ll sum, pmx, pmn; // subarray sum, prefix maximum, prefix minimum
Node() : sum(0), pmx(0), pmn(0) {}
Node(ll val) : sum(val), pmx(max(0ll, val)), pmn(min(0ll, val)) {}
friend Node operator+ (const Node &lhs, const Node &rhs)
{
Node res;
res.sum = lhs.sum + rhs.sum;
res.pmx = max(lhs.pmx, lhs.sum + rhs.pmx);
res.pmn = min(lhs.pmn, lhs.sum + rhs.pmn);
return res;
}
};
int n;
Node st[1 << 19];
Segtree() {}
Segtree(int n_) : n(n_) {}
inline void modify(int p, ll val)
{
const auto modify_ = [&](const auto &self, int node, int l, int r) -> void
{
if (l > p || r < p)
return;
if (p <= l && r <= p)
{
st[node] = Node(val);
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node] = st[node << 1] + st[node << 1 | 1];
};
modify_(modify_, 1, 0, n-1);
}
inline ll query(ll C)
{
const auto query_ = [&](const auto &self, int node, int l, int r) -> ll
{
if (l == r)
return max(min(C, st[node].sum), 0ll);
int mid = (l + r) >> 1;
if (st[node << 1 | 1].pmx - st[node << 1 | 1].pmn > C) // will reach the bound in later indices
return self(self, node << 1 | 1, mid+1, r);
ll res = self(self, node << 1, l, mid);
if (res + st[node << 1 | 1].pmx > C) // will go > C, the candies will be C until the prefix maximum
return C - (st[node << 1 | 1].pmx - st[node << 1 | 1].sum);
if (res + st[node << 1 | 1].pmn < 0) // will go < 0, the candies will go negative until the prefix minimum
return st[node << 1 | 1].sum - st[node << 1 | 1].pmn;
return res + st[node << 1 | 1].sum;
};
return query_(query_, 1, 0, n-1);
}
};
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> val)
{
int N = (int)C.size(), Q = (int)L.size();
vector<vector<ii>> op(N+1);
for (int i = 0; i < Q; ++i)
{
op[L[i]].pb({i, val[i]});
op[R[i]+1].pb({i, 0});
}
Segtree st = Segtree(Q);
vector<int> res(N);
for (int i = 0; i < N; ++i)
{
for (auto [id, v] : op[i])
st.modify(id, v);
res[i] = (int)st.query(C[i]);
}
return res;
}
