#include "candies.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 2e6+2;
vector <int> ans;
long long MIN(long long a, long long b)
{
if(a<b)return a;
return b;
}
long long MAX(long long a, long long b)
{
if(a>b)return a;
return b;
}
struct Segment
{
long long sum[MAXN],mn[MAXN],mx[MAXN];
void update(int v, int from, int to, int t, int delta)
{
if(from==to)
{
sum[v]+=delta;
mn[v] = sum[v];
mx[v] = sum[v];
return ;
}
int mid = (from+to)/2;
if(t<=mid)update(2*v,from,mid,t,delta);
else
update(2*v+1,mid+1,to,t,delta);
sum[v] = sum[2*v] + sum[2*v+1];
mn[v] = MIN(mn[2*v],sum[2*v]+mn[2*v+1]);
mx[v] = MAX(mx[2*v],sum[2*v]+mx[2*v+1]);
return ;
}
int query(int v, int from, int to, int c)
{
// cout<<v<<" "<<from<<" "<<to<<" "<<c<<" "<<sum[v]<<" "<<mn[v]<<" "<<mx[v]<<endl;
if(from==to)return MAX(0,MIN(sum[v],c));
int mid = (from+to)/2;
if(mx[2*v+1] - mn[2*v+1] > c)return query(2*v+1, mid+1, to, c);
int curr = query(2*v,from,mid,c);
// cout<<curr<<" "<<mn[2*v+1]<<" "<<sum[2*v+1]<<endl;
if(curr + mx[2*v+1] > c) return (c - (mx[2*v+1]-sum[2*v+1]));
if(curr + mn[2*v+1] < 0) return (sum[2*v+1]-mn[2*v+1]);
return curr + sum[2*v+1];
}
};
Segment S;
vector <pair <int,int> > curr[MAXN];
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 i,j;
int q = l.size();
for(i=0;i<q;i++)
{
curr[l[i]].push_back({i,v[i]});
curr[r[i]+1].push_back({i,-v[i]});
}
ans.resize(n);
for(i=0;i<n;i++)
{
for(auto p : curr[i])
{
S.update(1,0,q-1,p.first,p.second);
}
ans[i] = S.query(1,0,q-1,c[i]);// cout<<"OK"<<endl;
}
return ans;
}
