#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200005;
const ll INF = 1e18;
pair<ll,ll> segTree[4*maxn];
ll p[4*maxn];
void push(int l,int r,int indV)
{
segTree[indV].first += p[indV];
segTree[indV].second += p[indV];
if(l != r)
{
p[indV*2+1] += p[indV];
p[indV*2+2] += p[indV];
}
p[indV] = 0;
return ;
}
void modify(int lx,int rx,ll x,int l,int r,int indV)
{
push(l,r,indV);
if(l > rx || r < lx)
return ;
else if(l >= lx && r <= rx)
{
p[indV] += x;
push(l,r,indV);
return ;
}
int m = (l+r)/2;
modify(lx,rx,x,l,m,indV*2+1);
modify(lx,rx,x,m+1,r,indV*2+2);
segTree[indV] = {min(segTree[indV*2+1].first,segTree[indV*2+2].first),max(segTree[indV*2+1].second,segTree[indV*2+2].second)};
return ;
}
pair<ll,ll> get(int lx,int rx,int l,int r,int indV)
{
push(l,r,indV);
if(l > rx || r < lx)
return {INF,-INF};
else if(l >= lx && r <= rx)
return segTree[indV];
int m = (l+r)/2;
pair<ll,ll> sl = get(lx,rx,l,m,indV*2+1);
pair<ll,ll> sr = get(lx,rx,m+1,r,indV*2+2);
return {min(sl.first,sr.first),max(sl.second,sr.second)};
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
int n = c.size();
int q = l.size();
vector<vector<pair<int,int>>> ev(n+1);
for(int j = 0;j < q;++j)
{
ev[l[j]].push_back({v[j],j+1});
ev[r[j]+1].push_back({-v[j],j+1});
}
vector<int> s(n);
ll sum = 0;
for(int j = 0;j < n;++j)
{
for(int k = 0;k < ev[j].size();++k)
{
modify(ev[j][k].second,q,ev[j][k].first,0,q,0);
sum += ev[j][k].first;
}
push(0,q,0);
if(segTree[0].second - segTree[0].first < c[j])
{
s[j] = sum - segTree[0].first;
}
else
{
int lg = 0,rg = q;
while(lg < rg)
{
int mg = (lg+rg)/2;
pair<ll,ll> cc = get(mg,q,0,q,0);
if(cc.second-cc.first >= c[j])
{
lg = mg + 1;
}
else
rg = mg;
}
pair<ll,ll> cx = get(lg,q,0,q,0);
pair<ll,ll> cxd = get(lg-1,q,0,q,0);
if(cxd.first == cx.first)
{
s[j] = sum - cx.first;
}
else
s[j] = sum - cx.second + c[j];
}
}
return s;
}
