#include "candies.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
int cap[200005];
int val[200005];
long long valmax;
long long maxim[800005];
long long minim[800005];
long long lazy[800005];
long long typelazy[800005];
using namespace std;
pair<long long,int>vec[200005];
void push(int node,int st,int dr)
{
if(typelazy[node]==1)
{
maxim[node]=vec[dr].first;
if(st!=dr)
{
typelazy[node*2]=1;
typelazy[node*2+1]=1;
lazy[node*2]=0;
lazy[node*2+1]=0;
}
typelazy[node]=0;
}
if(typelazy[node]==-1)
{
maxim[node]=0;
if(st!=dr)
{
typelazy[node*2]=0;
typelazy[node*2+1]=0;
lazy[node*2]=0;
lazy[node*2+1]=0;
}
typelazy[node]=0;
}
if(lazy[node]!=0)
{
maxim[node]+=lazy[node];
if(st!=dr)
{
maxim[node*2]+=lazy[node];
maxim[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
}
void updatepoz(int node,int st,int dr,int val)
{
if(st==dr)
{
maxim[node]=min(vec[st].first,maxim[node]+val);
return;
}
int mij=(st+dr)/2;
push(node*2,st,mij);
push(node*2+1,mij+1,dr);
if(maxim[node*2]+val>vec[mij].first)
{
typelazy[node*2]=1;
push(node*2,st,mij);
updatepoz(node*2+1,mij+1,dr,val);
}
else
{
updatepoz(node*2,st,mij,val);
push(node*2+1,mij+1,dr);
}
maxim[node]=max(maxim[node*2],maxim[node*2+1]);
}
void updateneg(int node,int st,int dr,int val)
{
if(st==dr)
{
maxim[node]=max(0ll,maxim[node]+val);
return;
}
int mij=(st+dr)/2;
push(node*2,st,mij);
push(node*2+1,mij+1,dr);
if(maxim[node*2]+val<=0)
{
typelazy[node*2]=-1;
push(node*2,st,mij);
updateneg(node*2+1,mij+1,dr,val);
}
else
{
updateneg(node*2,st,mij,val);
lazy[node*2+1]=val;
push(node*2+1,mij+1,dr);
}
maxim[node]=max(maxim[node*2],maxim[node*2+1]);
}
vector<int>rasp;
void dfs(int node,int st,int dr)
{
push(node,st,dr);
if(st==dr)
{
rasp[vec[st].second-1]=maxim[node];
return;
}
int mij=(st+dr)/2;
dfs(node*2,st,mij);
dfs(node*2+1,mij+1,dr);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
int q = l.size();
for(int i=1;i<=n;i++)
{
vec[i].first=c[i-1];
vec[i].second=i;
}
sort(vec+1,vec+n+1);
for(int i=0;i<q;i++)
{
if(v[i]>=0)
updatepoz(1,1,n,v[i]);
else
updateneg(1,1,n,v[i]);
}
rasp.resize(n);
dfs(1,1,n);
return rasp;
}
