#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 2e5 + 5;
int c[lim], l[lim], r[lim], v[lim];
vector<int>event[lim];
struct Data{
ll s, mi, ma;
Data(){
s = mi = ma = 0;
}
Data(int x){
mi = min(0LL, s = x);
ma = max(0, x);
}
friend Data operator +(Data a, Data b){
Data c;
c.s = a.s + b.s;
c.mi = min(a.mi, a.s + b.mi);
c.ma = max(a.ma, a.s + b.ma);
return c;
}
};
Data st[lim << 2];
void update(int id, int l, int r, int p, int x){
if(l == r){
st[id] = Data(x);
return;
}
int m = (l + r) >> 1;
if(m < p){
update(id << 1 | 1, m + 1, r, p, x);
}
else{
update(id << 1, l, m, p, x);
}
st[id] = st[id << 1] + st[id << 1 | 1];
}
Data get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return Data();
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
}
vector<int>distribute_candies(vector<int>__c, vector<int>__l, vector<int>__r, vector<int>__v){
int n = __c.size(), q = __l.size();
for(int i = 0; i < n; i++){
c[i] = __c[i];
}
for(int i = 0; i < q; i++){
l[i] = __l[i];
r[i] = __r[i];
v[i] = __v[i];
}
vector<int>ans(n, 0);
if(max(n, q) <= 2000){
for(int i = 0; i < q; i++){
for(int j = l[i]; j <= r[i]; j++){
if(v[i] > 0){
ans[j] = min(c[j], ans[j] + v[i]);
}
else{
ans[j] = max(0, ans[j] + v[i]);
}
}
}
return ans;
}
if(*min_element(__v.begin(), __v.end()) > 0){
vector<ll>f(n + 1, 0);
for(int i = 0; i < q; i++){
f[l[i]] += v[i];
f[r[i] + 1] -= v[i];
}
ans[0] = min(ll(c[0]), f[0]);
for(int i = 1; i < n; i++){
ans[i] = min(ll(c[i]), f[i] += f[i - 1]);
}
return ans;
}
for(int i = 0; i < q; i++){
event[l[i]].push_back(i);
event[r[i] + 1].push_back(-i - 1);
}
set<int>sq;
for(int i = 0; i < n; i++){
for(int& j : event[i]){
if(j < 0){
int x = -j - 1;
sq.erase(x);
update(1, 0, q - 1, x, 0);
}
else{
sq.insert(j);
update(1, 0, q - 1, j, v[j]);
}
}
if(!sq.empty()){
int low = 0, high = q - 1;
while(low <= high){
int mid = (low + high) >> 1;
Data vl = get(1, 0, q - 1, mid, q - 1);
set<int>::iterator sq_it = sq.lower_bound(mid);
bool at0 = (sq_it == sq.begin() || v[*prev(sq_it)] < 0);
if(at0){
if(vl.mi < 0 || vl.ma > c[i]){
low = mid + 1;
}
else{
ans[i] = vl.ma;
high = mid - 1;
}
}
else if(vl.ma > 0 || vl.mi < -c[i]){
low = mid + 1;
}
else{
ans[i] = c[i] + vl.mi;
high = mid - 1;
}
}
}
}
return ans;
}
