#include "candies.h"
#include "bits/stdc++.h"
using namespace std;
#include <cassert>
#include <cstdio>
#include <vector>
struct segtree {
struct node {
int64_t upd = 0, mi = 0, ma = 0;
};
vector<node> st;
int64_t stok;
void push_down(int64_t idx) {
st[2*idx+1].upd += st[idx].upd;
st[2*idx+1].mi += st[idx].upd;
st[2*idx+1].ma += st[idx].upd;
st[2*idx+2].upd += st[idx].upd;
st[2*idx+2].mi += st[idx].upd;
st[2*idx+2].ma += st[idx].upd;
st[idx].upd = 0;
}
void u(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx, int64_t val) {
if(l <= constl && constr <= r) {
st[idx].upd += val;
st[idx].mi += val;
st[idx].ma += val;
return;
}
int64_t mid = (constl +constr) >> 1;
//almst forgot
push_down(idx);
if(mid <l || r <constl) u(l, r, mid+1, constr, 2*idx+2, val);
else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, val);
else{
u(l, r, constl, mid, 2*idx+1, val);
u(l, r, mid+1, constr, 2*idx+2, val);
}
st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
}
int64_t qu1(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx) {
if(l <= constl && constr <= r) return st[idx].mi;
int64_t mid = (constl + constr) >> 1;
push_down(idx);
if(mid< l || r<constl) return qu1(l, r, mid+1, constr, 2*idx+2);
else if(constr<l || r<mid+1) return qu1(l, r, constl, mid, 2*idx+1);
return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
}
int64_t qu2(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx) {
if(l <= constl && constr <= r) return st[idx].ma;
int64_t mid = (constl + constr) >> 1;
push_down(idx);
if(mid< l || r<constl) return qu2(l, r, mid+1, constr, 2*idx+2);
else if(constr<l || r<mid+1) return qu2(l, r, constl, mid, 2*idx+1);
return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
}
public:
void resize(int64_t k) {
stok = k;
st.resize(4*k + 10);
}
void range_add(int64_t l, int64_t r, int64_t v) {
u(l, r, 0, stok, 0, v);
}
int64_t query_min(int64_t l, int64_t r) {
return qu1(l, r, 0, stok, 0);
}
int64_t query_max(int64_t l, int64_t r) {
return qu2(l, r, 0, stok, 0);
}
};
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();
std::vector<int> s(n);
int q = l.size();
segtree owo;
owo.resize(q + 2);
owo.range_add(0, 0, 1e15);
owo.range_add(1, 1, 0);
vector<int> in[n+1], out[n+1];
for(int i=0; i<q; i++) {
in[l[i]].push_back(i);
out[r[i]+1].push_back(i);
}
for(int i=0; i<n; i++) {
for(int xxxX : in[i]) {
int x = xxxX + 2;
int val = v[xxxX];
owo.range_add(x, q + 1, val);
}
for(int xxxX: out[i]) {
int x = xxxX + 2;
int val = v[xxxX];
owo.range_add(x, q + 1, -val);
}
int lb = 0, rb = q + 1;
while(lb < rb) {
int mid = (lb + rb + 1) >> 1;
if(owo.query_max(mid, q + 1) - owo.query_min(mid, q + 1) >= c[i]) lb = mid;
else rb = mid - 1;
}
if(owo.query_max(lb, q + 1) - owo.query_min(lb, q + 1) >= c[i]) {
if(owo.query_max(lb, q + 1) == owo.query_max(lb, lb)) {
s[i] = owo.query_max(q + 1, q + 1) - owo.query_min(lb, q + 1);
}
else {
s[i] = owo.query_max(q + 1, q + 1) - (owo.query_max(lb, q + 1) - c[i]);
}
}
else {
s[i] = owo.query_max(q + 1, q + 1);
}
}
return s;
}
