#include <iostream>
#include <vector>
#include <algorithm>
// #include <queue>
using namespace std;
#define ll long long
#define INFI (ll)1000000000000000000
struct segTree{
int l; int r;
int lc, rc;
pair<ll, int> mx;
pair<ll, int> mn;
ll lazy;
segTree(int ind){
l = r = ind;
lc = rc = -1;
mx = mn = {(ll)0, ind};
lazy = (ll)0;
}
segTree(int indxInPool, int le, int ri){
l = le; r = ri;
lc = indxInPool*2 + 1;
rc = indxInPool*2 + 2;
mx = mn = {0, le};
lazy = 0;
}
};
vector<segTree> np;
void build (int l, int r, int ind){
if(l == r){
np[ind] = segTree(l);
return;
}
else{
np[ind] = segTree(ind, l, r);
build(l, (l+r)/2, np[ind].lc);
build((l+r)/2 + 1, r, np[ind].rc);
}
}
void update(int l, int r, ll x, int st){
np[st].mn.first += np[st].lazy;
np[st].mx.first += np[st].lazy;
if(np[st].l != np[st].r){
np[np[st].lc].lazy += np[st].lazy;
np[np[st].rc].lazy += np[st].lazy;
}
np[st].lazy = 0;
if(np[st].l == np[st].r){
np[st].mn.first += x;
np[st].mx.first += x;
np[st].lazy = 0;
return;
}
if(np[st].l == l && np[st].r == r){
np[np[st].lc].lazy += x;
np[np[st].rc].lazy += x;
np[st].mn.first += x;
np[st].mx.first += x;
np[st].lazy = 0;
return;
}
int mid = (np[st].l + np[st].r)/2;
if(l<=mid) update(l, min(r, mid), x, np[st].lc);
if(r>mid) update(max(mid+1, l), r, x, np[st].rc);
np[st].mn = min(make_pair(np[np[st].lc].mn.first + np[np[st].lc].lazy, np[np[st].lc].mn.second), {np[np[st].rc].mn.first + np[np[st].rc].lazy, np[np[st].rc].mn.second});
np[st].mx = max(make_pair(np[np[st].lc].mx.first + np[np[st].lc].lazy, np[np[st].lc].mx.second), {np[np[st].rc].mx.first + np[np[st].rc].lazy, np[np[st].rc].mx.second});
}
pair<ll, int> query(int md, int l, int r, int st){
if(l <= np[st].l && np[st].r <= r){
if(md == 0) return {np[st].mn.first + np[st].lazy, np[st].mn.second};
else return {np[st].mx.first + np[st].lazy, np[st].mx.second};
}
np[st].mn.first += np[st].lazy;
np[st].mx.first += np[st].lazy;
if(np[st].l != np[st].r){
np[np[st].lc].lazy += np[st].lazy;
np[np[st].rc].lazy += np[st].lazy;
}
np[st].lazy = 0;
if(np[st].l == np[st].r){
if(md == 0) return np[st].mn;
else return np[st].mx;
}
int mid = (np[st].l + np[st].r)/2;
if(md == 0){
pair<ll, int> ans = {INFI, INFI};
if(l <= mid) ans = min(ans, query(md, l, min(r, mid), np[st].lc));
if(r > mid) ans = min(ans, query(md, max(l, mid+1), r, np[st].rc));
return ans;
}
//if(md == 1){
pair<ll, int> ans = {-INFI, -INFI};
if(l <= mid) ans = max(ans, query(md, l, min(r, mid), np[st].lc));
if(r > mid) ans = max(ans, query(md, max(l, mid+1), r, np[st].rc));
return ans;
//}
}
int findMaxInd(ll c, int st, pair<ll, int> minR, pair<ll, int> maxR){
np[st].mn.first += np[st].lazy;
np[st].mx.first += np[st].lazy;
if(np[st].l != np[st].r){
np[np[st].lc].lazy += np[st].lazy;
np[np[st].rc].lazy += np[st].lazy;
}
np[st].lazy = 0;
if(np[st].l == np[st].r){
return np[st].l;
}
if(max(maxR.first, np[np[st].rc].mx.first + np[np[st].rc].lazy) - min(np[np[st].rc].mn.first + np[np[st].rc].lazy, minR.first) >= c){
return findMaxInd(c, np[st].rc, minR, maxR);
}
pair<ll, int> rMax = {np[np[st].rc].mx.first + np[np[st].rc].lazy, np[np[st].rc].mx.second};
pair<ll, int> rMin = {np[np[st].rc].mn.first + np[np[st].rc].lazy, np[np[st].rc].mn.second};
return findMaxInd(c, np[st].lc, min(minR,rMin), max(maxR, rMax));
}
vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v){
int q = v.size();
np.assign(4*(q+2), segTree(0));
vector<pair<int, pair<ll, ll>>> updL;
for(int i = 0; i<q; i++){
updL.push_back({l[i], {i+2, v[i]}});
}
vector<pair<int, pair<ll, ll>>> updR;
for(ll i = 0; i<q; i++){
updR.push_back({r[i], {i+2, v[i]}});
}
sort(updL.begin(), updL.end());
sort(updR.begin(), updR.end());
build(0, q+1, 0);
update(0, 0, INFI, 0);
vector<int> ans;
for(int i = 0; i<C.size(); i++){
ll c = C[i];
int le = upper_bound(updL.begin(), updL.end(), make_pair(i-1, make_pair(INFI, INFI))) - updL.begin();
int ri = upper_bound(updL.begin(), updL.end(), make_pair(i, make_pair(INFI, INFI))) - updL.begin()-1;
for(int j = le; j<=ri; j++) update(updL[j].second.first, q+1, updL[j].second.second, 0);
le = upper_bound(updR.begin(), updR.end(), make_pair(i-2, make_pair(INFI, INFI))) - updR.begin();
ri = upper_bound(updR.begin(), updR.end(), make_pair(i-1, make_pair(INFI, INFI))) - updR.begin()-1;
for(int j = le; j<=ri; j++) update(updR[j].second.first, q+1, -updR[j].second.second, 0);
le = findMaxInd(c, 0, {INFI, INFI}, {-INFI, -INFI});
auto maxInRange = query(1, le, q+1, 0);
auto minInRange = query(0, le, q+1, 0);
if(maxInRange.second > minInRange.second) ans.push_back(query(0, q+1, q+1, 0).first - query(0, maxInRange.second, maxInRange.second, 0).first + c);
else ans.push_back(query(0, q+1, q+1, 0).first - query(0, minInRange.second, minInRange.second, 0).first);
}
return ans;
}
