#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
vector<int>c, l, r, v;
namespace sub1{
vector<int>solve(){
vector<int>ans(n, 0);
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;
}
}
namespace sub2{
vector<int>solve(){
vector<int>ans(n, 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;
}
}
const int lim = 2e5 + 5;
namespace sub3{
pair<ll, ll>st[lim << 2];
ll lazy_1[lim << 2], lazy_2[lim << 2];
pair<ll, ll>merge(pair<ll, ll>a, pair<ll, ll>b){
return make_pair(min(a.first, b.first), max(a.second, b.second));
}
void propagate(int id, ll x){
st[id].first += x;
st[id].second += x;
lazy_1[id] += x;
}
void push_down(int id){
if(lazy_2[id] != -1){
lazy_2[id << 1] = lazy_2[id << 1 | 1] = st[id << 1].first = st[id << 1].second = st[id << 1 | 1].first = st[id << 1 | 1].second = lazy_2[id];
lazy_2[id] = -1;
}
propagate(id << 1, lazy_1[id]);
propagate(id << 1 | 1, lazy_1[id]);
lazy_1[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void refine(int id, int l, int r){
if(st[id].first > -1 && st[id].second <= c[0]){
return;
}
if(st[id].first >= c[0]){
st[id].first = st[id].second = lazy_2[id] = c[lazy_1[id] = 0];
return;
}
if(st[id].second < 1){
st[id].first = st[id].second = lazy_1[id] = lazy_2[id] = 0;
return;
}
int m = (l + r) >> 1;
push_down(id);
refine(id << 1, l, m);
refine(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
vector<int>ans;
void dfs(int id, int l, int r){
if(l == r){
ans.push_back(st[id].first);
return;
}
int m = (l + r) >> 1;
push_down(id);
dfs(id << 1, l, m);
dfs(id << 1 | 1, m + 1, r);
}
vector<int>solve(){
memset(lazy_1, 0, sizeof(lazy_1));
memset(lazy_2, -1, sizeof(lazy_2));
fill(st, st + (lim << 2), make_pair(0, 0));
for(int i = 0; i < q; i++){
update(1, 0, n - 1, l[i], r[i], v[i]);
refine(1, 0, n - 1);
}
dfs(1, 0, n - 1);
return ans;
}
}
vector<int>distribute_candies(vector<int>_c, vector<int>_l, vector<int>_r, vector<int>_v){
swap(c, _c);
swap(l, _l);
swap(r, _r);
swap(v, _v);
if(max(n = c.size(), q = l.size()) <= 2000){
return sub1::solve();
}
if(*min_element(v.begin(), v.end()) > 0){
return sub2::solve();
}
if(count(c.begin(), c.end(), c[0]) == n){
return sub3::solve();
}
}
