/*
https://oj.uz/problem/view/IOI21_candies
Distributing Candies
*/
#include <bits/stdc++.h>
using namespace std;
#define N 200000
#define Q 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N)) */
long long sum[N_ * 2], mn[N_ * 2], mx[N_ * 2]; int n_;
void pul(int i) {
int l = i << 1 | 0, r = i << 1 | 1;
sum[i] = sum[l] + sum[r];
mn[i] = min(mn[r], mn[l] + sum[r]);
mx[i] = max(mx[r], mx[l] + sum[r]);
}
void update(int i, int x) {
i |= n_;
sum[i] = x;
mn[i] = min(x, 0);
mx[i] = max(x, 0);
while (i > 1)
pul(i >>= 1);
}
int query(int c) {
long long s = 0, mn_ = 0, mx_ = 0;
int i = 1;
if (mx[1] - mn[1] <= c)
return mx[1];
while (i < n_)
if (max(mx_, mx[i << 1 | 1] + s) - min(mn_, mn[i << 1 | 1] + s) <= c) {
i = i << 1 | 0;
mn_ = min(mn_, mn[i ^ 1] + s);
mx_ = max(mx_, mx[i ^ 1] + s);
s += sum[i ^ 1];
} else
i = i << 1 | 1;
return min(max(sum[i] + s, mx_), c + mn_);
}
using vi = vector<int>;
vi distribute_candies(vi aa, vi ll, vi rr, vi vv) {
vector<array<int, 3>> ee;
int n, q, e;
vi ans;
n = aa.size(), q = ll.size();
for (int h = 0; h < q; h++) {
int l = ll[h], r = rr[h], v = vv[h];
ee.push_back({l, h, v});
ee.push_back({r + 1, h, 0});
}
n_ = 1;
while (n_ < q)
n_ <<= 1;
e = 0, sort(ee.begin(), ee.end());
for (int i = 0; i < n; i++) {
while (e < q * 2 && ee[e][0] <= i) {
update(ee[e][1], ee[e][2]);
e++;
}
ans.push_back(query(aa[i]));
}
return ans;
}
