#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector< int > add[N] , rem[N];
int n , m;
long long lazy[4 * N] ;
struct S{
long long mn , mx;
int mnIdx , mxIdx;
S(long long mn,long long mx){this->mn = mn, this->mx = mx;}
S(){mn = mx = 0;}
void make(const S & l , const S & r){
if(l.mn < r.mn)
mn = l.mn , mnIdx = l.mnIdx;
else
mn = r.mn , mnIdx = r.mnIdx;
if(r.mx >= l.mx)
mx = r.mx , mxIdx = r.mxIdx;
else
mx = l.mx , mxIdx = l.mxIdx;
}
} seg[4 * N];
void fix(int s,int e,int idx){
seg[idx].mn += lazy[idx];
seg[idx].mx += lazy[idx];
if(s != e){
lazy[(idx << 1)] += lazy[idx];
lazy[(idx << 1) + 1] += lazy[idx];
}
lazy[idx] = 0;
}
int l , r , val;
void build(int s,int e, int idx){
lazy[idx] = 0;
if(s == e){
seg[idx].mn = seg[idx].mx = 0;
seg[idx].mnIdx = seg[idx].mxIdx = s;
return;
}
build(s , ((s+e) >> 1),(idx << 1));
build(((s+e) >> 1) + 1,e,(idx << 1) + 1);
seg[idx].make(seg[(idx << 1)] , seg[(idx << 1) + 1]);
}
void update(int s,int e,int idx){
if(lazy[idx]) fix(s , e, idx);
if(s > r || e < l)
return;
if(s >= l && e <= r){
lazy[idx] += val;
fix(s , e, idx);
return;
}
update(s , (s + e) >> 1 , (idx << 1));
update(((s+e) >> 1) + 1, e , (idx << 1) + 1);
seg[idx].make(seg[(idx << 1)] , seg[(idx << 1) + 1]);
}
void getMx(int s,int e, int idx,long long &mxVal,int &mxIdx){
if(lazy[idx]) fix(s , e, idx);
if(s > r || e < l)
return;
if(s >= l && e <= r){
if(seg[idx].mx >= mxVal){
mxVal = seg[idx].mx;
mxIdx = seg[idx].mxIdx;
}
return;
}
getMx(s , ((s+e) >> 1),(idx << 1) , mxVal , mxIdx);
getMx(((s+e) >> 1) + 1, e , (idx << 1) + 1 , mxVal , mxIdx);
}
void getMn(int s,int e,int idx,long long& mnVal, int& mnIdx){
if(lazy[idx]) fix(s , e , idx);
if(s > r || e < l)
return;
if(s >= l && e <= r){
if(seg[idx].mn <= mnVal){
mnVal = seg[idx].mn;
mnIdx = seg[idx].mnIdx;
}
return;
}
getMn(s , ((s+e) >> 1),(idx << 1) , mnVal , mnIdx);
getMn(((s+e) >> 1) + 1, e , (idx << 1) + 1 , mnVal , mnIdx);
}
bool getFirstMn(int s,int e,int idx,long long &mnVal,int &mnIdx ,long long val){
//cout << s << " " << e << " " << idx << " " << l << " " << r << endl;
if(lazy[idx]) fix(s , e , idx);
if(s > r || e < l)
return false;
if(s >= l && e <= r){
//cout << "okay here ? " << s << " " << e << " " << seg[idx].mn << endl;
if(seg[idx].mn >= val) return false;
if(s == e){
mnVal = seg[idx].mn;
mnIdx = seg[idx].mnIdx;
return true;
}
if(lazy[(idx << 1) + 1]) fix(((s+e) >> 1) + 1 , e , (idx << 1) + 1);
if(seg[(idx << 1) + 1].mn < val)
return getFirstMn(((s+e) >> 1) + 1 , e , (idx << 1) + 1 , mnVal , mnIdx , val);
return getFirstMn(s , ((s+e) >> 1) , (idx << 1) , mnVal , mnIdx , val);
}
if(getFirstMn(((s+e) >> 1) + 1 , e , (idx << 1) + 1 , mnVal , mnIdx , val))
return true;
return getFirstMn(s , ((s+e) >> 1) , (idx << 1) , mnVal , mnIdx , val);
}
int solve(int c){
//cout << "----------------------------------------" << endl;
//cout << "solve " << c << endl;
long long mnVal , curMn , mxVal;
int mnIdx , curIdx , mxIdx;
l = 0 , r = m - 1;
mnVal = (long long)1e18;
getMn(0 , m - 1 , 1, mnVal , mnIdx);
//cout << mnIdx << " " << mnVal << endl;
int low = mnIdx + 1 , high = m - 1 , res = mnIdx , mid;
while(low <= high){
mid = (low + high) / 2;
//cout << "check " << mid << endl;
l = mid , r = m - 1;
curMn = (long long)1e18;
getMn(0 , m - 1 , 1 , curMn , curIdx);
//cout << "curMn =" << " " << curMn << " " << curIdx << endl;
l = mnIdx , r = curIdx;
if(!getFirstMn(0 , m - 1 , 1, curMn , curIdx , curMn)) cout << "what!!!?" << endl;
//cout << "one step to left " << curMn << " " << curIdx << " " << l << " " << r << endl;
l = curIdx , r = m - 1;
mxVal = -(long long)1e18;
getMx(0 , m - 1 , 1 , mxVal , mxIdx);
l = mxIdx , r = m - 1;
curMn = (long long)1e18;
getMn(0 , m - 1 , 1 , curMn , curIdx);
//cout << "check " << mid << endl;
//cout << mxIdx << " " << curIdx << " " << curMn << " " << mxVal << endl;
if(curIdx == mxIdx || (curMn + c - mxVal) >= 0)
high = mid - 1;
else
res = mid , low = mid + 1;
}
//cout << "done with res " << res << endl;
curMn = (long long)1e18;
l = r = m - 1;
getMn(0 , m - 1 , 1 , curMn , curIdx);
mnVal = (long long)1e18;
l = r = res;
getMn(0 , m - 1 , 1 ,mnVal , mnIdx);
mxVal = (long long)-1e18;
l = res , r = m - 1;
getMx(0 , m - 1 , 1 , mxVal , mxIdx);
//cout << mnIdx << " " << mxIdx << " " << curIdx << " " << mnVal << " " << mxVal << " " << curMn << endl;
if(mxIdx != mnIdx && mxVal - mnVal >= c){
return curMn - mxVal + c;
}
return curMn - mnVal;
}
vector< int > bruteforce(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
vector< int > s(n , 0);
int n = (int)c.size();
for(int i = 0 ;i < n;i++){
for(int j = 0 ;j < (int)l.size();j++){
if(l[j] <= i && r[j] >= i){
s[i] += v[j];
if(s[i] < 0) s[i] = 0;
if(s[i] > c[i]) s[i] = c[i];
}
}
}
return s;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
n = (int)c.size();
m = (int)l.size() + 1;
vector< int > s(n , 0);
for(int i = 0 ;i < n;i++){
add[i].clear();
rem[i].clear();
}
for(int i = 0 ;i < (int)l.size();i++){
add[l[i]].push_back(i);
rem[r[i] + 1].push_back(i);
}
build(0 , m - 1 , 1);
for(int i = 0 ;i < n;i++){
for(int j = 0 ;j < (int)add[i].size();j++){
::l = add[i][j] + 1;
::r = m - 1;
val = v[add[i][j]];
update(0 , m - 1 , 1);
}
for(int j = 0 ;j < (int)rem[i].size();j++){
::l = rem[i][j] + 1;
::r = m - 1;
val = -v[rem[i][j]];
update(0 , m - 1 , 1);
}
s[i] = solve(c[i]);
}
/*
vector< int > bf = bruteforce(c , l , r , v);
if(bf != s){
cout << "bad " << endl;
cout << "input: " << endl;
cout << (int)c.size() << endl;
for(int i = 0 ;i < (int)c.size();i++) cout << c[i] << " ";
cout << endl;
cout << (int)l.size() << endl;
for(int i = 0 ;i < (int)l.size();i++){
cout << l[i] << " " << r[i] << " " << v[i] << endl;
}
cout << "--------------------------" << endl;
for(int i = 0 ;i < (int)bf.size();i++){
cout << bf[i] << " ";
}
cout << endl;
}
*/
return s;
}
