#include "candies.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 1e6+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const ll INF = 2e18;
const int MOD = 998244353;
const int LOG = 20;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
ll n, q, a[MAXN], ans[MAXN], upd[MAXN];
vector<pii> vec[MAXN];
set<ll> s;
struct node {
ll mx, mn, sum;
} NOL;
node make(ll p){
node ret;
ret.mx = ret.mn = ret.sum = p;
return ret;
}
struct seg {
node st[4*MAXN];
node mrg(node a, node b){
node ret;
ret.mx = max(a.mx, a.sum+b.mx);
ret.mn = min(a.mn, a.sum+b.mn);
ret.sum = a.sum+b.sum;
return ret;
}
node upd(int id,int l,int r,int x,ll p){
if(l==r && l==x){
return st[id] = make(p);
}
if(r<x || x<l) return st[id];
return st[id] = mrg(upd(lf,l,md,x,p), upd(rg,md+1,r,x,p));
}
node que(int id,int l,int r,int x,int y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return NOL;
node le = que(lf,l,md,x,y), ri = que(rg,md+1,r,x,y);
if(le.mx == INF) return ri;
if(ri.mx == INF) return le;
return mrg(le, ri);
}
} A;
bool cek(ll idx, ll cap){
auto it = s.upper_bound(idx); it--;
// ll mn = INF, mx = -INF, v = 0;
// for(int i=idx+1; i<=q; i++){
// v += upd[i];
// chmn(mn, v); chmx(mx, v);
// }
ll mn = A.que(1,0,q,idx+1,q).mn, mx = A.que(1,0,q,idx+1,q).mx;
if(upd[*it] < 0){ // start di 0
if(mn < 0 || mx > cap) return 0;
} else { // start di cap
if(mn < -cap || mx > 0) return 0;
}
return 1;
}
ll get(ll idx, ll cap){
ll tot = A.que(1,0,q,idx+1,q).sum;
auto it = s.upper_bound(idx); it--;
// ll tot = 0;
// for(int i=idx+1; i<=q; i++) tot += upd[i];
if(upd[*it] < 0){ // start di 0
} else { // start di cap
tot += cap;
}
if(tot < 0 || tot > cap) assert(false);
return tot;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
NOL.mx = -INF;
n = c.size(); q = l.size();
for(int i=1; i<=n; i++) a[i] = c[i-1];
for(int i=1; i<=q; i++){
vec[l[i-1]+1].pb({i, v[i-1]});
vec[r[i-1]+2].pb({i, -v[i-1]});
}
s.insert(0); upd[0] = -1; // -
A.upd(1,0,q,0,-1);
for(int i=1; i<=n; i++){
for(auto [id, v] : vec[i]){
upd[id] += v;
A.upd(1,0,q,id, upd[id]);
if(upd[id] != 0) s.insert(id);
else s.erase(id);
}
// for(auto in : s) cout << in << ' ';
// cout << " s\n";
// for(int j=0; j<=q; j++) cout << upd[j] << " \n"[j==q];
// cout << " upd\n\n";
ll l=0, r=q, mid=0, cnt=-1;
while(l<=r){
mid = md;
// aman
if(cek(mid, a[i])) cnt = mid, r = mid-1;
else l = mid+1;
}
assert(cnt != -1);
// cout << i << ' '<< cnt << " \n\n";
ans[i] = get(cnt, a[i]);
}
std::vector<int> s(n);
for(int i=1; i<=n; i++) s[i-1] = (int)ans[i];
return s;
}
