#include "candies.h"
#include <bits/stdc++.h>
#define int long long
#define debug(x) if(0) cout << #x << " is " << x << endl;
#pragma GCC optimise("Ofast");
using namespace std;
vector<int> C, L, R, V;
const int INF = 1e18;
int N, Q;
struct mxsubarr{
int maxsum, sum, maxpref, maxsuf;
int32_t endidx, prefendidx;
mxsubarr(int a, int b, int c, int d, int e, int f){
maxsum = a;
sum = b;
maxpref = c;
maxsuf = d;
endidx = e;
prefendidx = f;
}
};
mxsubarr* merge(mxsubarr* l, mxsubarr* r){
int sum, maxpref, maxsuf, maxsum;
int32_t endidx, prefendidx;
sum = l->sum + r->sum;
maxpref = max(l->maxpref, l->sum + r->maxpref);
if(l->maxpref == maxpref) prefendidx = l->prefendidx;
else prefendidx = r->prefendidx;
maxsuf = max(r->maxsuf, r->sum + l->maxsuf);
maxsum = max({l->maxsum, r->maxsum, l->maxsuf + r->maxpref});
if(l->maxsum == maxsum) endidx = l->endidx;
else if(r->maxsum == maxsum) endidx = r->endidx;
else endidx = r->prefendidx;
mxsubarr* ret = new mxsubarr(maxsum, sum, maxpref, maxsuf, endidx, prefendidx);
return ret;
}
struct kadane{
int S, E, M;
mxsubarr* vals;
kadane *l, *r;
kadane(int _S, int _E){
S = _S;
E = _E;
M = (S + E) >> 1;
l = r = NULL;
vals = new mxsubarr(0, 0, 0, 0, S, S);
}
void upd(int idx, int val){
if(!l) l = new kadane(S, M);
if(!r) r = new kadane(M + 1, E);
if(S == E){
vals = new mxsubarr(val, val, val, val, S, S);
return;
}
if(idx <= M) l->upd(idx, val);
else r->upd(idx, val);
vals = merge(l->vals, r->vals);
}
int bsta(int goal, mxsubarr* right){
if(S == E){
auto k = merge(vals, right);
return k->endidx;
}
auto k = merge(r->vals, right);
if(k->maxsum >= goal){
return r->bsta(goal, right);
}
else{
return l->bsta(goal, k);
}
}
}*seggs1, *seggs2;
struct node{
//range add, range max, range min
int S, E, M, mn, mx, ladd;
node *l, *r;
node(int _S, int _E){
S = _S;
E = _E;
M = (S + E) >> 1;
mn = mx = ladd = 0;
if(S == E) return;
l = new node(S, M);
r = new node(M + 1, E);
}
void prop(){
if(S == E) return;
if(ladd != 0){
l->mn += ladd;
l->mx += ladd;
r->mn += ladd;
r->mx += ladd;
l->ladd += ladd;
r->ladd += ladd;
ladd = 0;
}
}
void upd(int start, int end, int val){
prop();
if(start == S && end == E){
ladd += val;
mn += val;
mx += val;
return;
}
if(end <= M){
l->upd(start, end, val);
}
else if(start > M){
r->upd(start, end, val);
}
else{
l->upd(start, M, val);
r->upd(M + 1, end, val);
}
mn = min(l->mn, r->mn);
mx = max(l->mx, r->mx);
}
int range_min(int start, int end){
prop();
if(start == S && end == E) return mn;
if(end <= M) return l->range_min(start, end);
else if(start > M) return r->range_min(start, end);
else return min(l->range_min(start, M), r->range_min(M + 1, end));
}
int range_max(int start, int end){
prop();
if(start == S && end == E) return mx;
if(end <= M) return l->range_max(start, end);
else if(start > M) return r->range_max(start, end);
else return max(l->range_max(start, M), r->range_max(M + 1, end));
}
}*seggs3;
vector<int32_t> distribute_candies(vector<int32_t> C, vector<int32_t> L, vector<int32_t> R, vector<int32_t> V) {
N = C.size();
Q = L.size();
debug(Q)
debug(N)
vector<int32_t> res(N, 0);
seggs1 = new kadane(0, Q + 5); //normal
seggs2 = new kadane(0, Q + 5); //negated
seggs3 = new node(0, Q + 5); //prefixsum
vector<int> add[N + 5];
vector<int> remove[N + 5];
for(int i=0;i<Q;i++){
add[L[i]].push_back(i);
remove[R[i]+1].push_back(i);
}
for(int i=0;i<N;i++){
for(auto j:add[i]){
seggs1->upd(j+1, V[j]);
seggs2->upd(j+1, -V[j]);
seggs3->upd(j+1, Q, V[j]);
}
for(auto j:remove[i]){
seggs1->upd(j+1, 0);
seggs2->upd(j+1, 0);
seggs3->upd(j+1, Q, -V[j]);
}
int lastmax = -1;
int lastmin = 0;
auto k = new mxsubarr(-1000, -1000, -1000, -1000, 69, 69);
if(seggs1->vals->maxsum >= C[i]) lastmax = seggs1->bsta(C[i], k);
if(seggs2->vals->maxsum >= C[i]) lastmin = seggs2->bsta(C[i], k);
if(lastmax > lastmin){
int k = C[i] + seggs3->range_max(Q, Q) - seggs3->range_max(lastmax, Q);
res[i] = k;
}
else{
int k = seggs3->range_max(Q, Q) - seggs3->range_min(lastmin, Q);
res[i] = k;
}
}
return res;
}
