#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll INF = 1e15;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
struct no{
ll mi = INF, ma = -INF;
int ind_mi = -1, ind_ma = -1;
};
no operator + (no A, no B) {
no C;
C.mi = min(A.mi, B.mi);
C.ma = max(A.ma, B.ma);
if(A.mi < B.mi) C.ind_mi = A.ind_mi;
else if(A.mi > B.mi) C.ind_mi = B.ind_mi;
else C.ind_mi = max(A.ind_mi, B.ind_mi);
if(A.ma < B.ma) C.ind_ma = B.ind_ma;
else if(A.ma > B.ma) C.ind_ma = A.ind_ma;
else C.ind_ma = max(A.ind_ma, B.ind_ma);
return C;
}
vl lazy;
vector<no> seg;
void build(int node, int l, int r) {
if(l == r) {
seg[node].mi = seg[node].ma = 0;
seg[node].ind_mi = seg[node].ind_ma = l;
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
seg[node] = seg[2*node] + seg[2*node+1];
}
void prop(int node, int l, int r) {
seg[node].mi += lazy[node];
seg[node].ma += lazy[node];
if(l != r) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int l, int r, int p, int q, int val) {
prop(node, l, r);
if(r < p or q < l) return;
if(p <= l and r <= q) {
lazy[node] = val;
prop(node, l, r);
return;
}
int mid = (l+r)/2;
update(2*node, l, mid, p, q, val);
update(2*node+1, mid+1, r, p, q, val);
seg[node] = seg[2*node] + seg[2*node+1];
}
no query(int node, int l, int r, int c, no at) {
prop(node, l, r);
if(l == r) return seg[node] + at;
int mid = (l+r)/2;
no suf = seg[2*node+1] + at;
if(suf.ma - suf.mi > c) return query(2*node+1, mid+1, r, c, at);
return query(2*node, l, mid, c, suf);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int N = sz(c), Q = sz(l);
lazy.resize(4*Q+10);
seg.resize(4*Q+10);
vector<vi> line(N);
for(int q = 0; q < Q; q++) {
line[l[q]].pb(q+1);
if(r[q]+1 != N) line[r[q]+1].pb(-q-1);
}
ll TOT = 0;
vi ans(N);
build(1, 0, Q);
for(int i = 0; i < N; i++) {
for(auto q : line[i]) {
if(q > 0) {
update(1, 0, Q, q, Q, v[q-1]);
TOT += v[q-1];
} else {
update(1, 0, Q, -q, Q, -v[-q-1]);
TOT -= v[-q-1];
}
}
no at;
at = query(1, 0, Q, c[i], at);
if(at.ma - at.mi <= c[i]) ans[i] = TOT;
else if(at.ind_ma >= at.ind_mi) ans[i] = c[i] - at.ma + TOT;
else ans[i] = TOT - at.mi;
}
return ans;
}
