#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> ii;
const int MAX=200005;
const long long INF=1e18;
int n,m;
long long Pmin[4*MAX],Pmax[4*MAX],lazy[4*MAX];
vector<ii> events[MAX];
void down(int k) {
Pmin[2*k]+=lazy[k],Pmin[2*k+1]+=lazy[k];
Pmax[2*k]+=lazy[k],Pmax[2*k+1]+=lazy[k];
lazy[2*k]+=lazy[k],lazy[2*k+1]+=lazy[k];
lazy[k]=0;
}
void update(int k,int l,int r,int L,int R,int val) {
if(l>R||L>r)
return;
if(L<=l&&r<=R) {
Pmin[k]+=val;
Pmax[k]+=val;
lazy[k]+=val;
return;
}
down(k);
int mid=(l+r)/2;
update(2*k,l,mid,L,R,val);
update(2*k+1,mid+1,r,L,R,val);
Pmin[k]=min(Pmin[2*k],Pmin[2*k+1]);
Pmax[k]=max(Pmax[2*k],Pmax[2*k+1]);
}
void update(int limit,int val) {
update(1,0,m,limit,m,val);
}
ii query(int k,int l,int r,int L,int R) {
if(l>R||L>r)
return {INF,-INF};
if(L<=l&&r<=R)
return {Pmin[k],Pmax[k]};
down(k);
int mid=(l+r)/2;
ii p1=query(2*k,l,mid,L,R);
ii p2=query(2*k+1,mid+1,r,L,R);
return {min(p1.first,p2.first),max(p1.second,p2.second)};
}
long long queryPmin(int limit) {
return query(1,0,m,limit,m).first;
}
long long queryPmax(int limit) {
return query(1,0,m,limit,m).second;
}
long long queryPos(int pos) {
return query(1,0,m,pos,pos).first;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n=c.size(),m=v.size();
for(int i=0;i<m;i++) {
events[l[i]].push_back({i+1,v[i]});
events[r[i]+1].push_back({i+1,-v[i]});
}
vector<int> rs(n);
for(int i=0;i<n;i++) {
// Update
for(ii event:events[i])
update(event.first,event.second);
// If all updates are in range
if(queryPmax(0)-queryPmin(0)<=c[i]) {
int l=1,r=m,pivot=0;
long long limit=queryPmin(0);
while(l<=r) {
int mid=(l+r)/2;
if(queryPmin(mid)==limit) {
l=mid+1;
pivot=mid;
}
else
r=mid-1;
}
rs[i]=queryPos(m)-queryPos(pivot);
continue;
}
int l=0,r=m,pivot;
while(l<=r) {
int mid=(l+r)/2;
if(queryPmax(mid)-queryPmin(mid)>c[i]) {
pivot=mid;
l=mid+1;
} else
r=mid-1;
}
// Find the last time touching the upper wall
if(queryPmin(pivot)==queryPos(pivot)) {
l=pivot+1,r=m;
long long limit=queryPmax(pivot);
while(l<=r) {
int mid=(l+r)/2;
if(queryPmax(mid)==limit) {
pivot=mid;
l=mid+1;
} else
r=mid-1;
}
rs[i]=c[i]+queryPos(m)-queryPos(pivot);
} else { // Find the last time touching the lower wall
l=pivot+1,r=m;
long long limit=queryPmin(pivot);
while(l<=r) {
int mid=(l+r)/2;
if(queryPmin(mid)==limit) {
pivot=mid;
l=mid+1;
} else
r=mid-1;
}
rs[i]=queryPos(m)-queryPos(pivot);
}
}
return rs;
}
