#include "candies.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int n, q;
struct SegmentTree
{
struct Node
{
llong minPrefix;
llong maxPrefix;
int minIdx;
int maxIdx;
llong sum;
Node()
{
sum = -INF;
}
};
Node tree[4*MAXN];
Node combine(Node left, Node right)
{
if (left.sum == -INF)
{
return right;
}
Node res;
res.sum = left.sum + right.sum;
if (left.minPrefix < left.sum + right.minPrefix)
{
res.minPrefix = left.minPrefix;
res.minIdx = left.minIdx;
} else
{
res.minPrefix = left.sum + right.minPrefix;
res.minIdx = right.minIdx;
}
if (left.maxPrefix > left.sum + right.maxPrefix)
{
res.maxPrefix = left.maxPrefix;
res.maxIdx = left.maxIdx;
} else
{
res.maxPrefix = left.sum + right.maxPrefix;
res.maxIdx = right.maxIdx;
}
return res;
}
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].minIdx = tree[node].maxIdx = l;
tree[node].minPrefix = tree[node].maxPrefix = tree[node].sum = 0;
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, int queryPos, int queryVal)
{
if (l == r)
{
tree[node].minIdx = tree[node].maxIdx = l;
tree[node].minPrefix = tree[node].maxPrefix = tree[node].sum = queryVal;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
Node query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node];
}
Node res;
int mid = (l + r) / 2;
if (queryL <= mid) res = combine(res, query(l, mid, 2*node, queryL, queryR));
if (mid + 1 <= queryR) res = combine(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
return res;
}
void build()
{
build(1, q + 2, 1);
}
void update(int pos, int val)
{
update(1, q + 2, 1, pos, val);
}
Node query(int l, int r)
{
return query(1, q + 2, 1, l, r);
}
};
SegmentTree tree;
std::vector <std::pair <int,int>> activate[MAXN];
std::vector <int> deactivate[MAXN];
std::vector<int> distribute_candies(std::vector <int> c, std::vector <int> l, std::vector <int> r, std::vector <int> v)
{
n = c.size();
q = l.size();
activate[0].push_back({INTINF, 1});
activate[0].push_back({-INTINF, 2});
for (int i = 0 ; i < q ; ++i)
{
activate[l[i]].push_back({v[i], i + 3});
deactivate[r[i] + 1].push_back(i + 3);
}
tree.build();
std::vector <int> ans(n);
for (int i = 0 ; i < n ; ++i)
{
for (const auto &[val, pos] : activate[i])
{
tree.update(pos, val);
}
for (const int &pos : deactivate[i])
{
tree.update(pos, 0);
}
int l = 1, r = q + 3, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
SegmentTree::Node res = tree.query(mid, q + 2);
if (res.maxPrefix - res.minPrefix >= c[i]) l = mid;
else r = mid;
}
SegmentTree::Node res = tree.query(l, q + 2);
if (res.maxIdx > res.minIdx)
{
llong lowerBound = tree.query(1, res.maxIdx).sum - c[i];
ans[i] = tree.tree[1].sum - lowerBound;
} else
{
llong lowerBound = tree.query(1, res.minIdx).sum;
ans[i] = tree.tree[1].sum - lowerBound;
}
}
return ans;
}
