#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> seg(1000001);
vector<pair<int,int>> wow(1000001);
int d;
void build(int l, int r, int x) {
seg[x] = {0,d-1};
wow[x] = {0,0};
if(l == r) {
return;
}
int m = (l+r)/2;
build(l,m,x*2);
build(m+1,r,x*2+1);
}
void upd(int l, int r, int x, int p, int br) {
if(l == r) {
if(br == INT_MAX) {
seg[x] = {0,d-1};
wow[x] = {0,0};
}
else {
if(br > 0) {
seg[x] = {min(br,d-1),d-1};
wow[x] = {0,min(br,d-1)};
}
else {
seg[x] = {0,max(0,d-1+br)};
wow[x] = {min(-br,d-1),0};
}
}
return;
}
int m = (l+r)/2;
if(p <= m) {
upd(l,m,x*2,p,br);
}
else {
upd(m+1,r,x*2+1,p,br);
}
int al,ar;
if(wow[x*2+1].first >= seg[x*2].first) {
al = seg[x*2+1].first;
}
else {
al = min(seg[x*2+1].second,seg[x*2+1].first+seg[x*2].first-wow[x*2+1].first);
}
if(wow[x*2+1].second >= d-1-seg[x*2].second) {
ar = seg[x*2+1].second;
}
else {
ar = max(seg[x*2+1].first,seg[x*2+1].second-(d-1-seg[x*2].second-wow[x*2+1].second));
}
seg[x] = {al,ar};
wow[x] = {wow[x*2+1].first+seg[x*2+1].first-al,wow[x*2+1].second+ar-seg[x*2+1].second};
}
void dude(int l, int r, int x) {
cout << l << " " << r << " " << seg[x].first << " " << seg[x].second << endl;
if(l == r) {
return;
}
int m = (l+r)/2;
dude(l,m,x*2);
dude(m+1,r,x*2+1);
}
vector<pair<int,int>> haha[300000];
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v) {
int n = c.size(),q = l.size();
d = c[0]+1;
build(0,q-1,1);
for(int i = 0; i < q; i++) {
haha[l[i]].push_back({v[i],i});
haha[r[i]+1].push_back({INT_MAX,i});
}
vector<int> ans(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < haha[i].size(); j++) {
upd(0,q-1,1,haha[i][j].second,haha[i][j].first);
}
ans[i] = seg[1].first;
// dude(0,q-1,1);
}
return ans;
}
