#include "candies.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
int C[200005];
int L[200005];
int R[200005];
int V[200005];
long long int B[200005];
int N, Q;
long long int D[200005];
typedef pair<long long int,long long int> P;
int sum(int a, int b) {
if(a>=b) return 0;
return B[b-1] - (a ? B[a-1] : 0);
}
const long long int INF = 1e18;
struct Node {
long long int mi, ma;
long long int p;
int mid, mad;
Node(long long int _i,long long int _a, long long int _p) : mi(_i), ma(_a), p(_p),mid(0),mad(0) {}
Node() : mi(INF),ma(-INF),p(0),mid(0),mad(0) {}
};
struct SegTree {
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
for(i=0;i<MAX;i++) {
seg[i].ma = 0;
seg[i].mi = 0;
seg[i].p = 0;
seg[i].mad = seg[i].mid = 0;
}
for(i=MAX/2;i<MAX;i++) seg[i].mad = seg[i].mid = i - MAX/2;
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = f(seg[2*i],seg[2*i+1]);
}
}
void prop(int n, int ns, int ne) {
if(!seg[n].p) return;
seg[n].ma += seg[n].p;
seg[n].mi += seg[n].p;
if(n<MAX/2) {
seg[2*n].p += seg[n].p;
seg[2*n+1].p += seg[n].p;
}
seg[n].p = 0;
}
Node f(Node x, Node y) {
Node c;
c.p = 0;
if(x.ma>y.ma) {
c.ma = x.ma;
c.mad = x.mad;
}
else if(x.ma<y.ma){
c.ma = y.ma;
c.mad = y.mad;
}
else {
c.ma = x.ma;
c.mad = max(x.mad, y.mad);
}
if(x.mi>y.mi) {
c.mi = y.mi;
c.mid = y.mid;
}
else if(x.mi<y.mi) {
c.mi = x.mi;
c.mid = x.mid;
}
else {
c.mi = x.mi;
c.mid = max(x.mid, y.mid);
}
return c;
}
void add(int s, int e, int k, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n].p += k;
prop(n,ns,ne);
return;
}
int mid = (ns + ne)/2;
add(s,e,k,2*n,ns,mid);
add(s,e,k,2*n+1,mid,ne);
if(n<MAX/2) {
seg[n] = f(seg[2*n],seg[2*n+1]);
}
}
void add(int s, int e, int k) {
add(s,e,k,1,0,MAX/2);
}
Node sum(int s, int e, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return Node();
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
return f(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
}
Node sum(int s, int e) {
return sum(s,e,1,0,MAX/2);
}
int find_pos(int l, int r, long long int C) {
if(l+1==r) return l;
int mid = l + r >> 1;
Node k = sum(mid, MAX/2, 1, 0, MAX/2);
if(k.ma - k.mi >= C) return find_pos(mid, r, C);
else return find_pos(l, mid, C);
}
};
vector<int> distribute_candies(vector<int> _C, vector<int> _L,
vector<int> _R, vector<int> _V) {
N = _C.size();
Q = _L.size();
register int i, j;
for(i=0;i<N;i++) C[i] = _C[i];
for(i=0;i<Q;i++) {
L[i] = _L[i];
R[i] = _R[i];
V[i] = _V[i];
R[i]++;
}
SegTree tree(Q+5);
tree.cons();
vector<vector<P>> Query;
Query.resize(N+1);
for(i=0;i<Q;i++) {
Query[L[i]].push_back(P(i,V[i]));
Query[R[i]].push_back(P(i,-V[i]));
}
vector<int> ans;
ans.resize(N);
for(i=0;i<N;i++) {
for(P k : Query[i]) {
tree.add(0, k.first + 1, k.second);
}
int pos = tree.find_pos(0, Q, C[i]);
Node k = tree.sum(pos, Q+1);
long long int pval = tree.sum(pos, pos+1).mi;
long long int mas = pval - k.mi;
long long int mis = pval - k.ma;
if(mas>=C[i]) {
ans[i] = C[i] + tree.sum(k.mid,k.mid+1).mi;
}
else if(mis<=-C[i]) {
ans[i] = tree.sum(k.mad,k.mad+1).mi;
}
else {
ans[i] = tree.sum(k.mad,k.mad+1).mi;
}
}
return ans;
}
