#include "candies.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
int n, q;
vector<int> op[200010];
struct {
struct {
long long maxx, minn, lz;
} node[800010];
void split(int id) {
node[id*2].maxx += node[id].lz;
node[id*2].minn += node[id].lz;
node[id*2+1].maxx += node[id].lz;
node[id*2+1].minn += node[id].lz;
node[id*2].lz += node[id].lz;
node[id*2+1].lz += node[id].lz;
node[id].lz = 0;
}
void update(int id, int x, int y, int pos, long long val) {
if (pos <= x) {
node[id].maxx += val;
node[id].minn += val;
node[id].lz += val;
return;
}
if (y < pos) return;
int mid = (x+y)/2;
split(id);
update(id*2,x,mid,pos,val);
update(id*2+1,mid+1,y,pos,val);
node[id].maxx = max(node[id*2].maxx,node[id*2+1].maxx);
node[id].minn = min(node[id*2].minn,node[id*2+1].minn);
}
long long findmax(int id, int x, int y, int pos) {
if (pos <= x) return node[id].maxx;
if (y < pos) return -1e18;
int mid = (x+y)/2;
split(id);
return max(findmax(id*2,x,mid,pos),findmax(id*2+1,mid+1,y,pos));
}
long long findmin(int id, int x, int y, int pos) {
if (pos <= x) return node[id].minn;
if (y < pos) return 1e18;
int mid = (x+y)/2;
split(id);
return min(findmin(id*2,x,mid,pos),findmin(id*2+1,mid+1,y,pos));
}
} seg;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n = c.size();
reverse(v.begin(),v.end());
reverse(l.begin(),l.end());
reverse(r.begin(),r.end());
l.push_back(0); l.push_back(0);
r.push_back(n-1); r.push_back(n-1);
v.push_back(-2e9); v.push_back(2e9);
reverse(v.begin(),v.end());
reverse(l.begin(),l.end());
reverse(r.begin(),r.end());
q = v.size();
vector<int> ans(n);
for (int i = 0; i < q; i++) {
op[l[i]].push_back(i);
op[r[i]+1].push_back(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < op[i].size(); j++) {
if (i == l[op[i][j]]) seg.update(1,0,q-1,op[i][j],v[op[i][j]]);
else seg.update(1,0,q-1,op[i][j],-v[op[i][j]]);
}
int l = 0, r = q-1;
while (l <= r) {
int mid = (l+r)/2;
if (seg.findmax(1,0,q-1,mid)-seg.findmin(1,0,q-1,mid) >= c[i]) l = mid+1;
else r = mid-1;
}
if (v[l] < 0) ans[i] = seg.findmax(1,0,q-1,q-1)-seg.findmin(1,0,q-1,l);
else ans[i] = c[i]-seg.findmax(1,0,q-1,l)+seg.findmin(1,0,q-1,q-1);
}
return ans;
}
