#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
const long long N = 200010;
long long c[N];
long long n;
struct Segtree{
long long tree[4*N];
array <long long, 3> lazy[4*N];
long long join(long long a, long long b){
return max(a, b);
}
void build(long long node, long long l, long long r){
lazy[node] = {0, 0, 0};
if(l == r){
tree[node] = 0;
return;
}
long long mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
}
void unlazy(long long node, long long l, long long r){
if(lazy[node][1] == 1){
tree[node] = 0;
}
else if(lazy[node][2] == 1){
tree[node] = c[r];
}
tree[node] += lazy[node][0];
if(l != r){
if(lazy[node][1] == 1 or lazy[node][2] == 1){
lazy[2*node] = lazy[2*node+1] = lazy[node];
}
else{
lazy[2*node][0] += lazy[node][0];
lazy[2*node+1][0] += lazy[node][0];
}
}
lazy[node] = {0, 0, 0};
}
void updateadd(long long node, long long l, long long r, long long tl, long long tr, long long val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lazy[node][0] += val;
unlazy(node, tl, tr);
return;
}
long long mid = (tl+tr)/2;
updateadd(2*node, l, r, tl, mid, val);
updateadd(2*node+1, l, r, mid+1, tr, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
void updateset(long long node, long long l, long long r, long long tl, long long tr, long long val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
lazy[node] = {0, 0, 0};
lazy[node][val] = 1;
unlazy(node, tl, tr);
return;
}
long long mid = (tl+tr)/2;
updateset(2*node, l, r, tl, mid, val);
updateset(2*node+1, l, r, mid+1, tr, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
long long query(long long node, long long l, long long r, long long tl, long long tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return 0;
if(l <= tl and tr <= r) return tree[node];
long long mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
long long busca(long long node,long long l, long long r, long long val){
unlazy(node, l, r);
if(val > 0){
if(l == r){
if(c[l]-tree[node] < val) return n+1;
return l;
}
long long mid = (l+r)/2;
unlazy(2*node, l, mid);
if(c[mid]-tree[2*node] >= val) return busca(2*node, l, mid, val);
return busca(2*node+1, mid+1, r, val);
}
else{
if(l == r){
if(tree[node] < val) return n+1;
return l;
}
long long mid = (l+r)/2;
unlazy(2*node, l, mid);
if(tree[2*node] >= val) return busca(2*node, l, mid, val);
return busca(2*node+1, mid+1, r, val);
}
}
} seg;
std::vector<int> distribute_candies(std::vector<int> cc, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
n = cc.size();
vector <pair <long long, long long>> maximos;
for(long long i = 0;i < n;i++){
maximos.push_back({cc[i], i});
}
sort(maximos.begin(), maximos.end());
for(long long j = 0;j < n;j++){
c[j+1] = maximos[j].first;
}
seg.build(1, 1, n);
for(auto x : v){
if(x > 0){
long long pos = seg.busca(1, 1, n, x);
//cout << pos << ' ';
seg.updateset(1, 1, pos-1, 1, n, 2);
seg.updateadd(1, pos, n, 1, n, x);
}
else{
long long pos = seg.busca(1, 1, n, x);
//cout << pos << ' ';
seg.updateset(1, 1, pos-1, 1, n, 1);
seg.updateadd(1,pos, n, 1, n, x);
}
}
vector <int> ans(n);
for(long long i = 0;i < n;i++){
ans[maximos[i].second] = seg.query(1, i+1, i+1, 1, n);
}
return ans;
}
