#include "candies.h"
#include <vector>
#include <iostream>
using namespace std;
const long long INF = 1'000'000'000'000'000'000;
struct segtree //min, max, range add
{
long long l;
long long r;
long long mn = 0;
long long mx = 0;
long long lp = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(long long L, long long R)
{
l = L;
r = R;
if(l == r) return;
long long m = (l+r+10)/2 - 5;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
long long rangemin(long long L, long long R)
{
if(R < l || r < L) return INF;
else if(L <= l && r <= R) return mn;
else return lp + min(left->rangemin(L, R), right->rangemin(L, R));
}
long long rangemax(long long L, long long R)
{
if(R < l || r < L) return -INF;
else if(L <= l && r <= R) return mx;
else return lp + max(left->rangemax(L, R), right->rangemax(L, R));
}
void add(long long L, long long R, long long V)
{
if(R < l || r < L) return;
// cerr << "adding to " << l << ' ' << r << ": " << L << ' ' << R << ' ' << V << '\n';
if(L <= l && r <= R)
{
mn += V;
mx += V;
lp += V;
}
else
{
left->add(L, R, V);
right->add(L, R, V);
mn = lp + min(left->mn, right->mn);
mx = lp + max(left->mx, right->mx);
}
}
};
vector<int> distribute_candies(vector<int> c1, vector<int> l1, vector<int> r1, vector<int> v1)
{
long long N = c1.size();
long long Q = l1.size();
vector<long long> c(N);
vector<long long> l(Q), r(Q), v(Q);
for(int i = 0; i < N; i++) c[i] = c1[i];
for(int j = 0; j < Q; j++)
{
l[j] = l1[j];
r[j] = r1[j];
v[j] = v1[j];
}
segtree S(-3, Q-1);
S.add(-3, -3, -INF);
S.add(-2, -2, +INF);
vector<long long> insertions[N], removals[N];
for(long long i = 0; i < Q; i++)
{
insertions[ l[i] ].push_back(i);
removals[ r[i] ].push_back(i);
}
vector<long long> res(N, 0);
long long curr_upd_sum = 0;
// for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' ';
// cerr << '\n';
for(long long i = 0; i < N; i++)
{
// cerr << "i = " << i << '\n';
for(long long o: insertions[i])
{
// cerr << "inserting " << o << ": " << l[o] << ' ' << r[o] << ' ' << v[o] << '\n';
S.add(o, Q-1, +v[o]);
curr_upd_sum += v[o];
// cerr << "segment tree: ";
// for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' ';
// cerr << '\n';
}
long long lower_bound = 0;
// cerr << S.rangemax(-1, Q-1) << ' ' << S.rangemin(-1, Q-1) << '\n';
long long last_good = Q-1;
// for(last_good = Q-1; last_good >= 0; last_good--)
// {
// if(S.rangemax(last_good-1, Q-1) - S.rangemin(last_good-1, Q-1) > (long long)c[i])
// break;
// }
// cerr << "last_good = " << last_good << '\n';
for(long long bit = 19; bit >= 0; bit--)
{
long long new_good = last_good - (1 << bit);
if(new_good < -1) continue;
if(S.rangemax(new_good, Q-1) - S.rangemin(new_good, Q-1) <= (long long)c[i])
last_good = new_good;
}
// cerr << "last_good = " << last_good << '\n';
if(0 <= S.rangemin(0, Q-1) && S.rangemax(0, Q-1) <= c[i])
lower_bound = 0;
else if(S.rangemax(last_good-1, last_good-1) < S.rangemax(last_good, last_good))
lower_bound = S.rangemax(last_good, Q-1) - (long long)c[i];
else
lower_bound = S.rangemin(last_good, Q-1);
// cerr << "curr_upd_sum = " << curr_upd_sum << ", lower_bound = " << lower_bound << '\n';
res[i] = (curr_upd_sum - lower_bound);
for(long long o: removals[i])
{
// cerr << "removing " << o << '\n';
S.add(o, Q-1, -v[o]);
curr_upd_sum -= v[o];
}
// cerr << "\n\n";
}
vector<int> res1(N);
for(int i = 0; i < N; i++) res1[i] = res[i];
return res1;
}
