#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
const int MAXN = 2e5+10;
using namespace std;
ll smx[MAXN*4], smn[MAXN*4], soma[MAXN*4];
int m(int l, int r){
return (l+r)>>1;
}
void update(int pos, int l, int r, int id, ll newVal){
if(l == r){
smx[pos] = smn[pos] = soma[pos] = newVal;
return;
}
if(id <= m(l,r))
update(pos<<1 , l , m(l,r), id, newVal);
else update(pos<<1|1, m(l,r)+1, r, id, newVal);
smx[pos] = max(smx[pos<<1], soma[pos<<1]+smx[pos<<1|1]);
smn[pos] = min(smn[pos<<1], soma[pos<<1]+smn[pos<<1|1]);
soma[pos] = soma[pos<<1]+soma[pos<<1|1];
}
ll qry(int pos, int l, int r, ll c){
if(l == r){
return min( max(0LL, soma[pos]), c );
}
if(smx[pos<<1|1]-smn[pos<<1] >= c)
return qry(pos<<1|1, m(l,r)+1, r, c);
ll rr = qry(pos<<1 , l , m(l,r), c);
if(rr+smx[pos<<1|1] > c)
return c+(soma[pos<<1|1]-smx[pos<<1|1]);
else if(rr+smn[pos<<1|1] < 0)
return (soma[pos<<1|1]-smn[pos<<1|1]);
return rr+soma[pos<<1|1];
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
int n = c.size();
int q = l.size();
vector<vector<int> > sweep(n+1);
for(int i = 0; i < q; i++){
sweep[l[i]].push_back(i+1);
sweep[r[i]+1].push_back(-i-1);
}
vector<int> ret;
for(int i= 0; i < n; i++){
for(auto &e : sweep[i]){
int id = e < 0 ? -e-1 : e-1;
update(1,0,n-1, id, e < 0 ? 0 : v[id]);
}
ret.push_back(qry(1,0,n-1, c[i]));
}
return ret;
}
