#include "candies.h"
#include <bits/stdc++.h>
#define SIZE 200001
using namespace std;
typedef long long ll;
ll lazy[4*SIZE], max_tree[4*SIZE], min_tree[4*SIZE];
vector<pair<int, int> > query[SIZE];
void pro(int node)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
max_tree[node*2]+=lazy[node];
max_tree[node*2+1]+=lazy[node];
min_tree[node*2]+=lazy[node];
min_tree[node*2+1]+=lazy[node];
lazy[node]=0;
}
void upd(int s, int e, int w, int l, int r, int node)
{
if (l>r) return;
if (s<=l && r<=e) {
lazy[node]+=w;
max_tree[node]+=w;
min_tree[node]+=w;
return;
}
if (l>e || s>r) return;
pro(node);
int mid=(l+r)/2;
upd(s, e, w, l, mid, node*2);
upd(s, e, w, mid+1, r, node*2+1);
max_tree[node]=max(max_tree[node*2], max_tree[node*2+1]);
min_tree[node]=min(min_tree[node*2], min_tree[node*2+1]);
}
ll get_max(int s, int e, int l, int r, int node)
{
if (l>r) return -1e18;
if (s<=l && r<=e) return max_tree[node];
if (l>e || s>r) return -1e18;
int mid=(l+r)/2;
pro(node);
return max(get_max(s, e, l, mid, node*2), get_max(s, e, mid+1, r, node*2+1));
}
ll get_min(int s, int e, int l, int r, int node)
{
if (l>r) return 1e18;
if (s<=l && r<=e) return min_tree[node];
if (l>e || s>r) return 1e18;
int mid=(l+r)/2;
pro(node);
return min(get_min(s, e, l, mid, node*2), get_min(s, e, mid+1, r, node*2+1));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int N=c.size(), M=l.size();
vector<int> ans(N);
for (int i=0; i<M; i++) {
query[l[i]].push_back(make_pair(v[i], i));
query[r[i]+1].push_back(make_pair(-v[i], i));
}
for (int i=0; i<N; i++) {
for (auto j : query[i]) upd(j.second+1, M, j.first, 0, M, 1);
if (get_max(0, M, 0, M, 1)-get_min(0, M, 0, M, 1)<=c[i]) ans[i]=get_max(M, M, 0, M, 1)-get_min(0, M, 0, M, 1);
else {
int s=0, e=M, mid;
while (1) {
if (s>=e) break;
mid=(s+e)/2;
if (get_max(mid, M, 0, M, 1)-get_min(mid, M, 0, M, 1)<=c[i]) e=mid;
else s=mid+1;
}
if (get_max(s-1, s-1, 0, M, 1)<get_min(s, M, 0, M, 1)) ans[i]=c[i]-get_max(s, M, 0, M, 1)+get_max(M, M, 0, M, 1);
else ans[i]=get_max(M, M, 0, M, 1)-get_min(s, M, 0, M, 1);
}
}
return ans;
}
