#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=200002;
ll inf=1e18;
struct Node {
ll m, M;
Node operator+(const Node &p) {
return {min(m, p.m), max(M, p.M)};
}
};
struct seg{
Node tree[4*MAX];
ll lazy[4*MAX];
void lazy_prop(int node, int s, int e) {
tree[node].m+=lazy[node];
tree[node].M+=lazy[node];
if(s!=e) {
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void update(int node, int s, int e, int l, int r, int v) {
lazy_prop(node, s, e);
if(s>r || e<l) return;
if(s>=l && e<=r) {
lazy[node]+=v;
lazy_prop(node, s, e);
return;
}
int m=s+e>>1;
update(node*2, s, m, l, r, v);
update(node*2+1, m+1, e, l, r, v);
tree[node]=tree[node*2]+tree[node*2+1];
}
int query(int node, int s, int e, ll c, ll m, ll M) {
lazy_prop(node, s, e);
if(s==e) {
if(max(tree[node].M, M)-min(tree[node].m, m)>c) return s;
return s-1;
}
int mid=s+e>>1;
lazy_prop(node*2, s, mid);
lazy_prop(node*2+1, mid+1, e);
pair<ll, ll> curr={min(m, tree[node*2+1].m), max(M, tree[node*2+1].M)};
if(curr.second-curr.first>c) return query(node*2+1, mid+1, e, c, m, M);
else return query(node*2, s, mid, c, curr.first, curr.second);
}
ll get(int node, int s, int e, int idx) {
lazy_prop(node, s, e);
if(s>idx || e<idx) return -1e18;
if(s==e) return tree[node].m;
int m=s+e>>1;
return max(get(node*2, s, m, idx), get(node*2+1, m+1, e, idx));
}
Node val(int node, int s, int e, int l, int r) {
lazy_prop(node, s, e);
if(s>r || e<l) return {inf, -inf};
if(s>=l && e<=r) return tree[node];
int m=s+e>>1;
return val(node*2, s, m, l, r)+val(node*2+1, m+1, e, l, r);
}
} tree;
struct query{
int s, v, idx;
bool operator<(const query &Q) const {
return s<Q.s;
}
};
vector<query> v;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> diff) {
int n = c.size(), q=r.size();
for(int i=0; i<q; i++) {
v.push_back({l[i], diff[i], i+1});
v.push_back({r[i]+1, -diff[i], i+1});
}
sort(v.begin(), v.end());
vector<int> ans(n);
int curr=0;
for(int i=0; i<n; i++) {
for(; curr<2*q; curr++) {
if(v[curr].s==i) tree.update(1, 0, q, v[curr].idx, q, v[curr].v);
else break;
}
int p=tree.query(1, 0, q, c[i], inf, -inf);
ll ed=tree.get(1, 0, q, q);
if(p==-1) {
Node cnt=tree.val(1, 0, q, 0, q);
ans[i]=ed-cnt.m;
continue;
}
Node cnt=tree.val(1, 0, q, p, q);
if(tree.get(1, 0, q, p)==cnt.m) ans[i]=c[i]-cnt.M+ed;
else ans[i]=ed-cnt.m;
}
return ans;
}
