#include "candies.h"
#include <bits/stdc++.h>
using ll = int64_t;
using namespace std;
//really fast iterative segment-tree implementation
template<class Segtree_Data>
struct Segment_Tree{
using T = typename Segtree_Data::node_t;
int n;
vector<T>data;
Segment_Tree(int n_) : n(n_), data(2*n, Segtree_Data::node_init()){
for(int i=n-1;i>=0;--i) data[i] = Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
}
Segment_Tree(vector<T> const&base) : n(base.size()), data(2*n, Segtree_Data::node_init()){
copy(base.begin(), base.end(), data.begin()+n);
for(int i=n-1;i>=0;--i) data[i] = Segtree_Data::merge_nodes(data[i<<1], data[i<<1|1]);
}
void update(int pos, typename Segtree_Data::update_t const&val){
for(Segtree_Data::update_node(data[pos+=n], val); pos>>=1;){
data[pos] = Segtree_Data::merge_nodes(data[pos<<1], data[pos<<1|1]);
}
}
void u(int pos, typename Segtree_Data::update_t const&val){
return update(pos,val);
}
T query(int l, int r) const {
T retL = Segtree_Data::node_ne(), retR = Segtree_Data::node_ne();
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1) retL = Segtree_Data::merge_nodes(retL, data[l++]);
if(r&1) retR = Segtree_Data::merge_nodes(data[--r], retR);
}
return Segtree_Data::merge_nodes(retL, retR);
}
T q(int l, int r) const {
return query(l, r);
}
};
constexpr ll inf = 2e18;
struct Node{
ll sum, min, max;
};
struct Segtreedata{
typedef Node node_t;
typedef int update_t;
static constexpr node_t node_init() {return Node{0, 0, 0};}
static constexpr node_t node_ne() {return Node{0, inf, -inf};}
static node_t merge_nodes(node_t const&left, node_t const&right){
return node_t{
left.sum + right.sum,
min(left.min, left.sum+right.min),
max(left.max, left.sum+right.max)
};
}
static void update_node(node_t &node, update_t const&update){
node = node_t{update, min(update, 0), max(update, 0)};
}
};
using Segtree = Segment_Tree<Segtreedata>;
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
const int n = c.size();
const int q = l.size();
vector<int> ret(n);
vector<vector<int> > ev(n+1);
for(int i=0; i<q; ++i){
ev[l[i]].push_back(i);
ev[r[i]+1].push_back(-1-i);
}
Segtree st(q);
for(int i=0; i<n; ++i){
for(auto const&e:ev[i]){
//cerr << "up " << e << "\n";
if(e >= 0) st.u(e, v[e]);
else st.u(-1-e, 0);
}
int l = 0, r = q+1;
auto span = st.q(0, q);
if(span.max - span.min <= c[i]){
// start at 0 -> won't hit top boundary -> ans is sum - min
ret[i] = span.sum - span.min;
continue;
}
while(l+1 < r){
const int m = l + (r-l) / 2;
span = st.q(m, q);
if(span.max - span.min <= c[i]){
r = m;
} else {
l = m;
}
}
span = st.q(l, q);
//cerr << span.min << " " << span.max << " " << span.sum << "\n";
assert(span.min == 0 || span.max == 0);
if(span.min == 0){
// won't hit bottom boundary -> ans is sum - max + c
ret[i] = span.sum - span.max + c[i];
} else {
// won't hit top boundary
ret[i] = span.sum - span.min;
}
}
return ret;
}
