#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;
bool cek(int idx, int 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);
}
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(int idx, int cap){
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;
}
return tot;
}
struct node {
ll mx, mn, sum;
};
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;
}
} A;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
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; // -
for(int i=1; i<=n; i++){
for(auto [id, v] : vec[i]){
upd[id] += v;
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;
}
