#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define INFI (ll)1000000000000000000
struct segTree{
ll l; ll r;
ll lc, rc;
pair<ll, ll> mx;
pair<ll, ll> mn;
ll lazy;
segTree(ll ind){
l = r = ind;
lc = rc = -1;
mx = mn = {0, ind};
lazy = 0;
}
segTree(ll indxInPool, ll le, ll ri){
l = le; r = ri;
lc = indxInPool*2 + 1;
rc = indxInPool*2 + 2;
mx = mn = {0, le};
lazy = 0;
}
};
vector<segTree> np;
void build (ll l, ll r){
queue<pair<ll, ll>> todo;
todo.push({l, r});
while(!empty(todo)){
l = todo.front().first;
r = todo.front().second;
todo.pop();
ll i = np.size();
if(l == r){
np.push_back(segTree(l));
continue;
}
np.push_back(segTree(i, l, r));
todo.push({l, (l+r)/2});
todo.push({(l+r)/2 + 1, r});
}
}
void update(ll l, ll r, ll x, ll 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;
}
ll 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, ll> query(ll md, ll l, ll r, ll 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){
if(md == 0) return np[st].mn;
else return np[st].mx;
}
ll mid = (np[st].l + np[st].r)/2;
if(md == 0){
pair<ll, ll> 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, ll> 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;
//}
}
ll findMaxInd(ll c, ll st, pair<ll, ll> minR, pair<ll, ll> 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, ll> rMax = {np[np[st].rc].mx.first + np[np[st].rc].lazy, np[np[st].rc].mx.second};
pair<ll, ll> 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){
ll q = v.size();
vector<pair<ll, pair<ll, ll>>> updL;
for(ll i = 0; i<q; i++){
updL.push_back({l[i], {i+2, v[i]}});
}
vector<pair<ll, 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);
update(0, 0, INFI, 0);
vector<int> ans;
for(ll i = 0; i<C.size(); i++){
ll c = C[i];
ll le = upper_bound(updL.begin(), updL.end(), make_pair(i-1, make_pair(INFI, INFI))) - updL.begin();
ll ri = upper_bound(updL.begin(), updL.end(), make_pair(i, make_pair(INFI, INFI))) - updL.begin()-1;
for(ll 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(ll 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;
}
