#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
const int maxn = 2e5 + 10;
const ll inf = 1e13;
struct Evento{
int prior, id, val; Evento( int prior, int id, int val ) : prior(prior), id(id), val(val) {}
bool operator < ( Evento e ){
return (( prior == e.prior ) ? abs(val) > abs(e.val) : prior < e.prior );
}
};
class Segment_Tree{
private:
struct Node{
pll mini, maxi;
ll tot;
Node(){
mini = pll( inf, 0 );
maxi = pll( -inf, 0 );
tot = 0;
}
Node( pll val ) : mini(val), maxi(val), tot(val.first) {}
Node operator + ( Node n ){
Node resp;
resp.mini = min( mini, pll( tot + n.mini.first, n.mini.second ) );
resp.maxi = max( maxi, pll( tot + n.maxi.first, n.maxi.second ) );
resp.tot = tot + n.tot;
return resp;
}
};
vector<Node> seg;
int n;
void update( int pos, int ini, int fim, int id, int val ){
if( ini > id || id > fim ) return;
if( ini == fim ){ seg[pos] = Node( pll( seg[pos].tot + val, ini ) ); return; }
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
update( l, ini, mid, id, val ); update( r, mid + 1, fim, id, val );
seg[pos] = seg[l] + seg[r];
}
Node query( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return seg[0];
if( ki <= ini && fim <= kf ) return seg[pos];
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}
public:
void update( int id, int val ){ update( 1, 0, n - 1, id, val ); }
int query( ll val ){
int l = (( seg[1].mini.first <= 0 ) ? seg[1].mini.second + 1 : 0 );
int r = n - 1;
if( l > r ) return 0;
while( l < r ){
int mid = ( l + r + 1 )/2;
Node x = query( 1, 0, n - 1, mid, n - 1 );
if( x.mini.first <= -val || x.maxi.first >= val || x.maxi.first - x.mini.first >= val ) l = mid;
else r = mid - 1;
}
Node x = query( 1, 0, n - 1, r, n - 1 );
if( x.maxi.first >= val )
return val + query( 1, 0, n - 1, x.maxi.second + 1, n - 1 ).tot;
return query( 1, 0, n - 1, x.mini.second + 1, n - 1 ).tot;
}
Segment_Tree( int n ) : n(n){ seg.resize(4*n); }
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v ){
int n = c.size(), q = l.size();
vector<Evento> line;
for( int i = 0; i < n; i++ ) line.push_back( Evento( i, i, 0 ) );
for( int i = 0; i < q; i++ ){
line.push_back( Evento( l[i], i, v[i] ) );
line.push_back( Evento( r[i] + 1, i, -v[i] ) );
}
sort( line.begin(), line.end() );
Segment_Tree seg(q);
vector<int> resp(n);
for( auto x : line ){
if( x.val != 0 ) seg.update( x.id, x.val );
else resp[x.id] = seg.query(c[x.id]);
}
return resp;
}
