#include<bits/stdc++.h>
#include "candies.h"
using namespace std;
const long long INF = 1e18;
class Tree{
private:
int lrSize = 2;
vector<long long> maxVal;
vector<long long> minVal;
vector<long long> lazy;
void update(int pos, bool up){
minVal[pos] = min(minVal[2*pos], minVal[2*pos+1]);
maxVal[pos] = max(maxVal[2*pos], maxVal[2*pos+1]);
if(pos > 1 && up)update(pos/2, true);
}
void push(int pos){
minVal[2*pos] += lazy[pos];
maxVal[2*pos] += lazy[pos];
lazy[2*pos] += lazy[pos];
minVal[2*pos + 1] += lazy[pos];
maxVal[2*pos + 1] += lazy[pos];
lazy[2*pos + 1] += lazy[pos];
lazy[pos] = 0;
}
void rangeAdd(int a, int b, int l, int r, int pos, long long val){
if(b < l || r < a)return;
if(a <= l && r <= b){
minVal[pos] += val; maxVal[pos] += val;
lazy[pos] += val;
}else{
int m = (l + r) / 2;
push(pos);
rangeAdd(a, b, l, m, 2*pos, val);
rangeAdd(a, b, m+1, r, 2*pos + 1, val);
update(pos, false);
}
}
public:
Tree(int n){
while(lrSize < n)lrSize *= 2;
maxVal.resize(2*lrSize, 0);
minVal.resize(2*lrSize, 0);
lazy.resize(2*lrSize, 0);
}
void add(int a, long long val){
rangeAdd(a, lrSize-1, 0, lrSize-1, 1, val);
}
long long getAns(long long c){
long long maxV = -INF;
long long minV = INF;
int pos = 1;
while(pos < lrSize){
push(pos);
if(max(maxVal[2*pos + 1], maxV) - min(minVal[2*pos + 1], minV) >= c){
pos = 2*pos + 1;
}else{
maxV = max(maxV, maxVal[2*pos + 1]);
minV = min(minV, minVal[2*pos + 1]);
pos = 2 * pos;
}
}
long long val1 = minVal[pos];
pos = 1;
while(pos < lrSize){
push(pos);
pos = 2*pos + 1;
}
long long val2 = minVal[pos];
//cout<<"Debug info "<<val1<<" "<<val2<<"\n";
if(val1 < minV){
return c - (maxV - val2);
}else{
return (val2 - minV);
}
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size();
int q = l.size();
vector<int> s(n);
vector<vector<int>> add(n);
vector<vector<int>> remove(n);
for(int i = 0; i < q; i++){
add[l[i]].push_back(i);
remove[r[i]].push_back(i);
}
Tree tree(q + 2);
tree.add(0, INF);
tree.add(1, -INF);
for(int i = 0; i < n; i++){
for(auto x : add[i]){
tree.add(x + 2, v[x]);
}
s[i] = tree.getAns(c[i]);
for(auto x : remove[i]){
tree.add(x+2, -v[x]);
}
}
return s;
}
