#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,bmi,bmi2")
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll M[1000000] = {0}, m[1000000] = {0}, lazy[1000000] = {0};
void push(int v)
{
M[2 * v] += lazy[v];
M[2 * v + 1] += lazy[v];
m[2 * v] += lazy[v];
m[2 * v + 1] += lazy[v];
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, ll dx)
{
if (r < tl || tr < l)
return;
if (l <= tl && tr <= r)
{
M[v] += dx;
m[v] += dx;
lazy[v] += dx;
return;
}
push(v);
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, r, dx);
update(2 * v + 1, tm + 1, tr, l, r, dx);
M[v] = max(M[2 * v], M[2 * v + 1]);
m[v] = min(m[2 * v], m[2 * v + 1]);
}
ll Find(int v, int tl, int tr, ll Mx, ll Mn, int c)
{
if (tl == tr)
return tl;
push(v);
int tm = (tl + tr) / 2;
if (max(Mx, M[2 * v + 1]) - min(Mn, m[2 * v + 1]) <= c)
return Find(2 * v, tl, tm, max(Mx, M[2 * v + 1]), min(Mn, m[2 * v + 1]), c);
return Find(2 * v + 1, tm + 1, tr, Mx, Mn, c);
}
ll Max(int v, int tl, int tr, int l, int r)
{
if (r < tl || tr < l)
return LLONG_MIN;
if (l <= tl && tr <= r)
return M[v];
push(v);
int tm = (tl + tr) / 2;
return max(
Max(2 * v, tl, tm, l, r),
Max(2 * v + 1, tm + 1, tr, l, r)
);
}
ll Min(int v, int tl, int tr, int l, int r)
{
if (r < tl || tr < l)
return LLONG_MAX;
if (l <= tl && tr <= r)
return m[v];
push(v);
int tm = (tl + tr) / 2;
return min(
Min(2 * v, tl, tm, l, r),
Min(2 * v + 1, tm + 1, tr, l, r)
);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int n = c.size(), q = v.size();
vector<vector<pair<int,int>>> events(n+1);
events[0].push_back({1000000000, -2});
events[0].push_back({-1000000000, -1});
for (int i = 0; i < q; i++)
{
events[l[i]].push_back({v[i], i});
events[r[i]+1].push_back({-v[i], i});
}
vector<int> s(n);
int j = 0;
ll sum = 0;
for (int i = 0; i < n; i++)
{
for (auto [val, time] : events[i])
{
sum += val;
update(1, 0, q + 1, time + 2, q + 1, val);
}
int idx = Find(1, 0, q + 1, sum, sum, c[i]);
if (Max(1, 0, q + 1, idx + 1, q + 1) <= Max(1, 0, q + 1, idx, idx))
s[i] = sum - Min(1, 0, q + 1, idx + 1, q + 1);
else
s[i] = c[i] - (Max(1, 0, q + 1, idx + 1, q + 1) - sum);
}
return s;
}
