// Starcraft 2 enjoyer //
#include "candies.h"
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 2e5 + 5;
const int M = 11;
const int B = 18;
const long long K = 2;
const int LG = 20;
const long long INF = 1e18 + 5;
const int P = 31;
const int MOD = 998244353;
const int nx[] = {0, 1, 0, -1}, ny[] = {-1, 0, 1, 0};
struct Node
{
long long sum, pref, mx, mn;
Node operator+(Node a)
{
Node ans;
ans.mn = min(a.mn, a.sum + mn);
ans.mx = max(a.mx, a.sum + mx);
ans.pref = min(a.pref, a.sum + pref);
ans.sum = sum + a.sum;
return ans;
}
};
struct SegmentTree
{
vector<Node> st;
int n;
void build(int v, int l, int r)
{
if (l == r)
{
st[v].mn = st[v].mx = st[v].sum = st[v].pref = 0;
}
else
{
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
st[v] = st[2 * v] + st[2 * v + 1];
}
}
void update(int v, int val, int pos, int l, int r)
{
if (l == r)
{
st[v].sum = val;
st[v].mx = val > 0 ? val : 0;
st[v].mn = val < 0 ? val : 0;
st[v].pref = val < 0 ? val : 0;
}
else
{
int m = (l + r) / 2;
if (pos <= m)
{
update(2 * v, val, pos, l, m);
}
else
{
update(2 * v + 1, val, pos, m + 1, r);
}
st[v] = st[2 * v] + st[2 * v + 1];
}
}
int lowerbound(int v, int val, int l, int r)
{
if (l == r)
{
// cout << st[v].mx << " " << st[v].mn << " " << l << "\n";
if (st[v].mx - st[v].mn < val)
return l - 1;
return l;
}
else
{
int m = (l + r) / 2;
if (st[2 * v + 1].mx - st[2 * v + 1].mn >= val)
{
return lowerbound(2 * v + 1, val, m + 1, r);
}
else
{
return lowerbound(2 * v, val - st[2 * v + 1].sum, l, m);
}
}
}
int lastmn(int v, int val, int l, int r)
{
if (l == r)
{
return l;
}
else
{
int m = (l + r) / 2;
if (st[2 * v + 1].mn > val)
{
return lastmn(2 * v, val - st[2 * v + 1].sum, l, m);
}
else
{
return lastmn(2 * v + 1, val, m + 1, r);
}
}
}
int lastmx(int v, int val, int l, int r)
{
if (l == r)
{
return l;
}
else
{
int m = (l + r) / 2;
if (st[2 * v + 1].mx < val)
{
return lastmn(2 * v, val - st[2 * v + 1].sum, l, m);
}
else
{
return lastmn(2 * v + 1, val, m + 1, r);
}
}
}
int firstpref(int v, int val, int l, int r)
{
if (l == r)
{
return l;
}
else
{
int m = (l + r) / 2;
if (st[2 * v].pref > val)
{
return firstpref(2 * v + 1, val - st[2 * v].sum, m + 1, r);
}
else
{
return firstpref(2 * v, val, l, m + 1);
}
}
}
Node get(int v, int l, int r, int tl, int tr)
{
if (tl > tr)
return {0, 0, 0};
else if (tl <= l && r <= tr)
{
return st[v];
}
else
{
int m = (l + r) / 2;
return get(2 * v, l, m, tl, min(tr, m)) + get(2 * v + 1, m + 1, r, max(tl, m + 1), tr);
}
}
SegmentTree(int len)
{
n = len;
st.assign(4 * n, {});
build(1, 0, n - 1);
}
void update(int val, int pos)
{
update(1, val, pos, 0, n - 1);
}
int lowerbound(int v)
{
return lowerbound(1, v, 0, n - 1);
}
int lastmn(int val)
{
return lastmn(1, val, 0, n - 1);
}
int lastmx(int val)
{
return lastmx(1, val, 0, n - 1);
}
int firstpref(int val)
{
return firstpref(1, val, 0, n - 1);
}
Node get(int l, int r)
{
if (l > r)
return {0, 0, 0, 0};
return get(1, 0, n - 1, l, r);
}
};
int n, q;
vector<pair<int, int>> update[N];
vector<int> ans;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
n = c.size(), q = l.size();
ans.assign(n, 0);
SegmentTree st(q);
for (int x = 0; x < q; x++)
{
update[l[x]].push_back({v[x], x});
update[r[x] + 1].push_back({0, x});
}
for (int x = 0; x < n; x++)
{
for (auto &[v, i] : update[x])
{
st.update(v, i);
}
int i = st.lowerbound(c[x]);
// cout << i << " " << x << "\n";
if (i == -1)
{
int j = st.firstpref(st.get(0, q - 1).pref);
ans[x] = max(st.get(j, q - 1).sum, st.get(j + 1, q - 1).sum);
}
else if (i == q - 1)
{
if (st.get(i, q - 1).sum >= c[x])
{
ans[x] = c[x];
}
else
{
ans[x] = 0;
}
}
else
{
Node nd = st.get(i, q - 1);
// cout << nd.mn << " " << nd.mx << " " << nd.pref << " " << nd.sum << " " << x << "\n";
if (nd.sum == nd.mx)
{
int j = st.lastmn(nd.mn);
ans[x] = c[x] + min(st.get(j, q - 1).sum, st.get(j + 1, q - 1).sum);
}
else
{
int j = st.lastmx(nd.mx);
ans[x] = min(st.get(j, q - 1).sum, st.get(j + 1, q - 1).sum);
}
}
}
// for (int x = 0; x < n; x++)
// {
// cout << ans[x] << " ";
// }
// cout << "\n";
return ans;
}
