#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10,lg=19,kaf=(1<<lg);
long long allc[maxn];
long long inf=1e15+5;
vector<pair<long long,long long>>insq[maxn],ersq[maxn];
long long n,q;
struct segment{
struct node{
long long suma,ted,lazy;
pair<long long ,long long>maxa,mina;
node(){
suma=ted=lazy=0;
mina=make_pair(0,0);
maxa=make_pair(0,0);
}
};
node seg[(1<<(lg+1))];
segment(){
for(long long i=kaf*2-1;i>=0;i--){
if(i>=kaf){
seg[i].mina.second=seg[i].maxa.second=(i-kaf);
seg[i].maxa.second*=-1;
seg[i].ted=1;
}else{
seg[i].ted=seg[(i<<1)].ted+seg[(i<<1)^1].ted;
seg[i].mina.second=seg[(i<<1)].mina.second;
seg[i].maxa.second=seg[(i<<1)].maxa.second;
}
}
}
void calc(long long i){
if(i>=kaf){
seg[i].suma+=seg[i].lazy;
seg[i].mina.first+=seg[i].lazy;
seg[i].maxa.first+=seg[i].lazy;
seg[i].lazy=0;
return ;
}
seg[i].maxa=max(make_pair(seg[(i<<1)].maxa.first+seg[(i<<1)].lazy,seg[(i<<1)].maxa.second),make_pair(seg[(i<<1)^1].maxa.first+seg[(i<<1)^1].lazy,seg[(i<<1)^1].maxa.second));
seg[i].mina=min(make_pair(seg[(i<<1)].mina.first+seg[(i<<1)].lazy,seg[(i<<1)].mina.second),make_pair(seg[(i<<1)^1].mina.first+seg[(i<<1)^1].lazy,seg[(i<<1)^1].mina.second));
}
void shift(long long i){
if(i>=kaf){
return ;
}
seg[(i<<1)].lazy+=seg[i].lazy;
seg[(i<<1)^1].lazy+=seg[i].lazy;
seg[i].lazy=0;
}
void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
seg[i].lazy+=w;
shift(i);
calc(i);
return ;
}
long long m=(l+r)>>1;
shift(i);
upd((i<<1),l,m,tl,tr,w);
upd((i<<1)^1,m+1,r,tl,tr,w);
calc(i);
return ;
}
long long porssum(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr){
return 0;
}
shift(i);
calc(i);
if(l>=tl&&r<=tr){
return seg[i].suma;
}
long long m=(l+r)>>1;
return porssum((i<<1),l,m,tl,tr)+porssum((i<<1)^1,m+1,r,tl,tr);
}
pair<long long ,long long> porsmax(long long i,long long l,long long r,long long tl,long long tr,long long w=0){
shift(i);
calc(i);
if(l>r||l>tr||r<tl||tl>tr){
return make_pair(-inf,-1);
}
if(l>=tl&&r<=tr){
return seg[i].maxa;
}
long long m=(l+r)>>1;
return max(porsmax((i<<1),l,m,tl,tr,w),porsmax((i<<1)^1,m+1,r,tl,tr,w));
}
pair<long long ,long long> porsmin(long long i,long long l,long long r,long long tl,long long tr,long long w=0){
shift(i);
calc(i);
if(l>r||l>tr||r<tl||tl>tr){
return make_pair(inf,-1);
}
if(l>=tl&&r<=tr){
return seg[i].mina;
}
long long m=(l+r)>>1;
return min(porsmin((i<<1),l,m,tl,tr,w),porsmin((i<<1)^1,m+1,r,tl,tr,w));
}
}seg;
long long tof=0;
long long solve2(int l,int r,long long w){
//cout<<l<<" "<<r<<" "<<w<<endl;
pair<long long ,long long>mx=seg.porsmax(1,0,kaf-1,l+1,r),mn=seg.porsmin(1,0,kaf-1,l+1,r);
mx.second*=-1;
mx.first-=seg.porssum(1,0,kaf-1,l,l);
mn.first-=seg.porssum(1,0,kaf-1,l,l);
//cout<<mn.first<<" "<<mn.second<<endl;
if(tof==0){
if(mn.first<0){
tof=0;
return solve2(mn.second,q,w);
}
if(mx.first>w){
tof=1;
return solve2(mx.second,q,w);
}
}else{
if(mn.first<-w){
tof=0;
return solve2(mn.second,q,w);
}
if(mx.first>0){
tof=1;
return solve2(mx.second,q,w);
}
}
long long res=seg.porssum(1,0,kaf-1,q,q)-seg.porssum(1,0,kaf-1,l,l);
// //cout<<"chyshod: "<<l<<" "<<r<<" "<<w<<" "<<seg.porssum(1,0,kaf-1,q,q)<<" "<<seg.porssum(1,0,kaf-1,l,l)<<" "<<res<<endl;
if(tof==1){
res=w+res;
tof=0;
}
return res;
}
long long solve(long long l,long long r,long long w){
//cout<<l<<" "<<r<<" "<<w<<endl;
if(l==r){
//cout<<l<<" "<<r<<" "<<seg.porssum(1,0,kaf-1,q,q)<<" "<<seg.porssum(1,0,kaf-1,l,l)<<endl;
long long res=seg.porssum(1,0,kaf-1,q,q)-seg.porssum(1,0,kaf-1,l,l);
// if(tof==1){
// res=w+res;
//}
if(l<q&&seg.porsmax(1,0,kaf-1,l,q).first==seg.porssum(1,0,kaf-1,l,l)){
res=w+res;
}
return res;
}
long long mid=(l+r)>>1;
if(seg.porsmax(1,0,kaf-1,mid+1,r).first==seg.porssum(1,0,kaf-1,mid,mid)&&seg.porsmin(1,0,kaf-1,mid+1,r).first==seg.porssum(1,0,kaf-1,mid,mid)){
return solve(l,mid,w);
}
if(seg.porsmax(1,0,kaf-1,l-(l>0),mid).first==seg.porsmin(1,0,kaf-1,l-(l>0),mid).first){
return solve(mid+1,r,w);
}
//cout<<"wtf: "<<l<<" "<<r<<" "<<seg.porsmax(1,0,kaf-1,l,r).first<<" "<<seg.porsmax(1,0,kaf-1,l,r).second<<" "<<seg.porsmin(1,0,kaf-1,l,r).first<<" "<<seg.porsmin(1,0,kaf-1,l,r).second<<endl;
pair<long long ,long long>mx=seg.porsmax(1,0,kaf-1,l,r),mn=seg.porsmin(1,0,kaf-1,l,r);
if(mx.first<w){
mx.second=-1;
}
if(mn.first>=0){
mn.second=-1;
}
if(max(mx.second,mn.second)>mid){
if(mx.second<=mid){
tof=0;
}else if(mn.second<=mid){
tof=1;
}else if(mx.second<mn.second){
tof=1;
}else{
tof=0;
}
return solve(mid+1,r,w);
}
//cout<<l<<" "<<r<<" "<<w<<endl;
long long indmax=seg.porsmax(1,0,kaf-1,l,mid,seg.porsmax(1,0,kaf-1,mid+1,q).first).second,indmin=-seg.porsmin(1,0,kaf-1,l,mid,seg.porsmin(1,0,kaf-1,mid+1,r).first).second;
if(indmax>indmin){
indmin=-seg.porsmin(1,0,kaf-1,mid+1,r).second;
////cout<<"wtffffff: "<<seg.porssum(1,0,kaf-1,indmax,indmax)<<" "<<seg.porssum(1,0,kaf-1,indmin,indmin)<<" "<<indmax<<" "<<indmin<<endl;
if(seg.porssum(1,0,kaf-1,indmax,indmax)-seg.porssum(1,0,kaf-1,indmin,indmin)>=w){
tof=0;
return solve(mid+1,r,w);
}
}else{
indmax=seg.porsmax(1,0,kaf-1,mid+1,r).second;
////cout<<"wtffffff: "<<seg.porssum(1,0,kaf-1,indmax,indmax)<<" "<<seg.porssum(1,0,kaf-1,indmin,indmin)<<" "<<indmax<<" "<<indmin<<endl;
if(seg.porssum(1,0,kaf-1,indmax,indmax)-seg.porssum(1,0,kaf-1,indmin,indmin)>=w){
tof=1;
return solve(mid+1,r,w);
}
}
return solve(l,mid,w);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n=c.size();
q=l.size();
for(long long i=0;i<n;i++){
allc[i]=c[i];
}
for(long long i=0;i<q;i++){
insq[l[i]].push_back(make_pair(i+1,v[i]));
ersq[r[i]+1].push_back(make_pair(i+1,v[i]));
}
vector<int>ret;
for(long long i=0;i<n;i++){
tof=0;
for(auto x:insq[i]){
seg.upd(1,0,kaf-1,x.first,q,x.second);
}
for(auto x:ersq[i]){
seg.upd(1,0,kaf-1,x.first,q,-x.second);
}
ret.push_back(solve2(0,q,allc[i]));
}
return ret;
}
