#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> vec;
const int N=2e5+100;
int seg[4*N];
int seg2[4*N];
void fix(int p,int s,int e)
{
if(s!=e){
if(seg2[p]){
seg[p*2]=0;
seg[p*2+1]=0;
seg2[p*2]=seg2[p];
seg2[p*2+1]=seg2[p];
}
if(seg[p]){
seg[p*2]+=seg[p];
seg[p*2+1]+=seg[p];
seg[p]=0;
}
}
else{
if(seg2[p]==1){
seg[p]+=vec[s].first;
}
if(seg2[p]==-1){
seg[p]+=0;
}
}
seg2[p]=0;
}
void build(int p,int s,int e)
{
cout<<p<<" "<<s<<" "<<e<<" "<<seg[p]<<" "<<seg2[p]<<endl;
if(s==e)return;
int mid=(s+e)/2;
build(p*2,s,mid);
build(p*2+1,mid+1,e);
}
int get(int p,int s,int e,int i)
{
fix(p,s,e);
if(s==e){
return seg[p];
}
int mid=(s+e)/2;
if(i<=mid){
return get(p*2,s,mid,i);
}
else{
return get(p*2+1,mid+1,e,i);
}
}
void update1(int p,int s,int e,int a,int b,int v)
{
fix(p,s,e);
if(a<=s&&b<=e){
seg[p]+=v;
fix(p,s,e);
return;
}
if(s>b||e<a)return;
int mid=(s+e)/2;
update1(p*2,s,mid,a,b,v);
update1(p*2+1,mid+1,e,a,b,v);
}
void update2(int p,int s,int e,int a,int b,int v)
{
fix(p,s,e);
if(a<=s&&e<=b){
seg2[p]=v;
seg[p]=0;
fix(p,s,e);
return;
}
if(s>b||e<a)return;
int mid=(s+e)/2;
update2(p*2,s,mid,a,b,v);
update2(p*2+1,mid+1,e,a,b,v);
}
vector<int> distribute_candies(vector<int> c,vector<int> l,
vector<int> r,vector<int> v){
int n=c.size();
int m=l.size();
vector<int> ans(n);
for(int i=0;i<n;i++){
vec.push_back({c[i],i});
}
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
for(int i=0;i<m;i++){
int l=0,r=n-1,ann=-1;
while(l<=r){
int mid=(l+r)/2;
if(0<=get(1,0,n-1,mid)+v[i]&&get(1,0,n-1,mid)+v[i]<=vec[mid].first){
// cout<<"mid "<<mid<<" "<<get(1,0,n-1,mid)<<" "<<v[i]<<" "<<vec[i].first<<endl;
ann=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(ann!=-1)update1(1,0,n-1,0,ann,v[i]);
if(ann!=n-1){
if(v[i]>0)update2(1,0,n-1,ann+1,n-1,+1);
else update2(1,0,n-1,ann+1,n-1,-1);
}
/* cout<<ann<<endl;
for(int i=0;i<n;i++){
cout<<get(1,0,n-1,i)<<" ";
}
cout<<endl;
// cout<<endl;
// build(1,0,n-1);
// cout<<endl;
*/
}
for(int i=0;i<vec.size();i++){
auto x= vec[i];
ans[x.second]=get(1,0,n-1,i);
}
return ans;
}
