#include "candies.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
long long n,q;
vector<pair<long long,long long>> haha[200001];
vector<pair<long long,long long>> big(1000001);
vector<pair<long long,long long>> sm(1000001);
vector<long long> wow(1000001);
void build(long long l, long long r, long long x) {
if(l == r) {
big[x] = {0,l};
sm[x] = {0,-l};
return;
}
long long mid = (l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
big[x] = max(big[x*2],big[x*2+1]);
sm[x] = min(sm[x*2],sm[x*2+1]);
}
void upd(long long l, long long r, long long ql, long long qr, long long x, long long br) {
if(l == ql && r == qr) {
wow[x]+=br;
big[x] = {big[x].first+br,big[x].second};
sm[x] = {sm[x].first+br,sm[x].second};
return;
}
long long mid = (l+r)/2;
if(qr <= mid) {
upd(l,mid,ql,qr,x*2,br);
}
else if(ql > mid) {
upd(mid+1,r,ql,qr,x*2+1,br);
}
else {
upd(l,mid,ql,mid,x*2,br);
upd(mid+1,r,mid+1,qr,x*2+1,br);
}
big[x] = max(big[x*2],big[x*2+1]);
sm[x] = min(sm[x*2],sm[x*2+1]);
big[x] = {big[x].first+wow[x],big[x].second};
sm[x] = {sm[x].first+wow[x],sm[x].second};
}
pair<long long,long long> calc(long long l, long long r, long long ql, long long qr, long long x, bool y) {
if(ql > qr) {
return {0,-1};
}
if(l == ql && r == qr) {
if(y) {
return big[x];
}
else {
return sm[x];
}
}
long long mid = (l+r)/2;
pair<long long,long long> ans;
if(qr <= mid) {
ans = calc(l,mid,ql,qr,x*2,y);
}
else if(ql > mid) {
ans = calc(mid+1,r,ql,qr,x*2+1,y);
}
else {
pair<long long,long long> a = calc(l,mid,ql,mid,x*2,y);
pair<long long,long long> b = calc(mid+1,r,mid+1,qr,x*2+1,y);
if(y) {
ans = max(a,b);
}
else {
ans = min(a,b);
}
}
ans = {ans.first+wow[x],ans.second};
return ans;
}
long long dude(long long l, long long r, long long x, long long c, long long big1, long long sm1, long long d) {
if(l == r) {
big1 = max(big1,big[x].first+d);
sm1 = min(sm1,sm[x].first+d);
if(big1-sm1 >= c) {
return l-1;
}
else {
return l;
}
}
d+=wow[x];
int mid = (l+r)/2;
long long big2 = max(big1,big[x*2].first+d);
long long sm2 = min(sm1,sm[x*2].first+d);
if(big2-sm2 < c) {
return dude(mid+1,r,x*2+1,c,big2,sm2,d);
}
else {
return dude(l,mid,x*2,c,big1,sm1,d);
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size();
q = l.size();
for(long long i = 0; i < q; i++) {
haha[l[i]].push_back({v[i],q+1-i});
haha[r[i]+1].push_back({-v[i],q+1-i});
}
q++;
build(1,q,1);
vector<int> ans(n);
for(long long i = 0; i < n; i++) {
for(pair<long long,long long> v: haha[i]) {
upd(1,q,v.second,q,1,v.first);
}
long long p = dude(1,q,1,c[i],0,0,0);
if(p == q) {
ans[i] = calc(1,q,1,q,1,1).first;
}
else {
p++;
pair<long long,long long> a = calc(1,q,1,p,1,1);
pair<long long,long long> b = calc(1,q,1,p,1,0);
b = {b.first,-b.second};
if(b.second > a.second) {
ans[i] = a.first;
}
else {
ans[i] = c[i]+b.first;
}
}
}
return ans;
}
