#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int N= 2e5+5;
pair<int,int> mn[4*N],mx[4*N];
int lazy[4*N];
void applay(int node, int val) {
mx[node].ff += val;
mn[node].ff += val;
lazy[node] += val;
}
void push(int node) {
if (lazy[node] != 0) {
applay(node*2,lazy[node]);
applay(node*2+1,lazy[node]);
lazy[node] = 0;
}
}
void update(int node, int l, int r, int L, int R, int val) {
if (l > R || r < L) return;
if (l >= L && r <= R) {
applay(node,val);
return;
}
push(node);
int mid = (l+r)/2;
update(node*2,l,mid,L,R,val);
update(node*2+1,mid+1,r,L,R,val);
mn[node] = min(mn[node*2],mn[node*2+1]);
mx[node] = max(mx[node*2],mx[node*2+1]);
}
pair <int,int> getmax(int node, int l, int r, int L, int R) {
if (l > R || r < L) return {-1e9,-1e9};
if (l >= L && r <= R) return mx[node];
push(node);
int mid = (l+r)/2;
return max(getmax(node*2,l,mid,L,R),getmax(node*2+1,mid+1,r,L,R));
}
pair <int,int> getmin(int node, int l, int r, int L, int R) {
if (l > R || r < L) return {1e9,1e9};
if (l >= L && r <= R) return mn[node];
push(node);
int mid = (l+r)/2;
return min(getmin(node*2,l,mid,L,R),getmin(node*2+1,mid+1,r,L,R));
}
int get(int x,int q) {
return getmax(1,0,q,x,x).ff;
}
void build(int node, int l, int r) {
if (l == r) {
mx[node] = {0,l};
mn[node] = {0,l};
return;
}
int mid = (l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
int q = l.size();
vector <vector<pair<int,int>>> res(n+5);
build(1,0,q);
for (int i = 0; i < q; i++) {
res[l[i]].emplace_back(i+1,v[i]);
if (r[i] != n-1) res[r[i]+1].emplace_back(i+1,-v[i]);
}
vector <int> s(n);
for (int i = 0; i < n; i++) {
for (auto [pos,val]:res[i]) {
update(1,0,q,pos,q,val);
}
int sum = get(q,q);
if (mx[1].ff-mn[1].ff <= c[i]) {
s[i] = sum-mn[1].ff;
continue;
}
int l = 1; int r = q;
int ans = -1;
while (l <= r) {
int mid = (l+r)/2;
if (getmax(1,0,q,mid,q).ff-getmin(1,0,q,mid,q).ff >= c[i]) {
ans = mid;
l = mid + 1;
} else {
r = mid -1;
}
}
auto mx1 = getmax(1,0,q,ans,q);
auto mn1 = getmin(1,0,q,ans,q);
if (mx1.ss <= mn1.ss) {
s[i] = sum-mn1.ff;
} else {
s[i] = c[i]+(sum-mx1.ff);
}
}
return s;
}
