#include <iostream>
#include <fstream>
#include <vector>
#include "candies.h"
using namespace std;
const int nmax=200010, qmin=0, qmax=1;
const long long inf=10000000000LL;
int Q;
struct Node {long long ma,mi,lazy; int ima,imi;};
Node tree[nmax*4];
void build(int u,int A,int B){
if (A==B) {
tree[u].ima=tree[u].imi=A;
return;
}
int C=(A+B)/2;
int left=u<<1; int right=left+1;
build(left,A,C); build(right,C+1,B);
tree[u].imi=tree[right].imi;
tree[u].ima=tree[right].ima;
}
void update(int u, int A, int B, int a, int b,long long val){
if (b<A || a>B) return;
if (a<=A && B<=b) {
tree[u].lazy+=val; return;
}
int C=(A+B)/2;
int left=2*u; int right=left+1;
if (tree[u].lazy!=0){
tree[left].lazy+=tree[u].lazy;
tree[right].lazy+=tree[u].lazy;
tree[u].mi+=tree[u].lazy;
tree[u].ma+=tree[u].lazy;
tree[u].lazy=0;
}
update(left,A,C,a,b,val); update(right,C+1,B,a,b,val);
// change max
if (tree[left].ma+tree[left].lazy >
tree[right].ma+tree[right].lazy){
tree[u].ma=tree[left].ma+tree[left].lazy;
tree[u].ima=tree[left].ima;
} else {
tree[u].ma=tree[right].ma+tree[right].lazy;
tree[u].ima=tree[right].ima;
}
// change min
if (tree[left].mi+tree[left].lazy <
tree[right].mi+tree[right].lazy){
tree[u].mi=tree[left].mi+tree[left].lazy;
tree[u].imi=tree[left].imi;
} else {
tree[u].mi=tree[right].mi+tree[right].lazy;
tree[u].imi=tree[right].imi;
}
}
pair <long long, int>
getans(int u, int A, int B, int a, int b, int reg){
if (b<A || a>B) {
if (reg==qmax) return make_pair(-2*inf,-1);
else return make_pair(2*inf,-1);
}
if (a<=A && B<=b) {
if (reg==qmax)
return make_pair(tree[u].ma+tree[u].lazy,tree[u].ima);
else
return make_pair(tree[u].mi+tree[u].lazy,tree[u].imi);
}
int C=(A+B)/2;
int left=2*u; int right=left+1;
if (tree[u].lazy!=0){
tree[left].lazy+=tree[u].lazy;
tree[right].lazy+=tree[u].lazy;
tree[u].mi+=tree[u].lazy;
tree[u].ma+=tree[u].lazy;
tree[u].lazy=0;
}
pair <long long, int>
maleft= getans(left,A,C,a,b,reg),
maright=getans(right,C+1,B,a,b,reg);
if (reg==qmax) {
if (maleft.first>maright.first) return maleft;
else return maright;
} else {
if (maleft.first<maright.first) return maleft;
else return maright;
}
}
//**************************************************
vector <int> distribute_candies
(vector<int>c, vector<int>l, vector<int>r, vector<int>v){
int n=c.size(), q=l.size();
vector <int> qon[n],qoff[n];
vector <int> indon[n],indoff[n];
vector <int> ans;
build(1,0,q+1);
update(1,0,q+1,0,q+1,+inf);
update(1,0,q+1,1,q+1,-inf);
for (int i=0;i<q;i++){
int x1=l[i], x2=r[i];
qon[x1].push_back(v[i]); qoff[x2].push_back(-v[i]);
indon[x1].push_back(i+2); indoff[x2].push_back(i+2);
}
for (int i=0;i<n;i++){
int cnt=qon[i].size();
for (int j=0;j<cnt;j++)
update(1,0,q+1,indon[i][j],q+1,qon[i][j]);
pair <long long, int> ma,mi;
long long res;
int A=0,B=q+1;
while (A<B){
int C=(A+B+1)/2;
mi=getans(1,0,q+1,C,q+1,qmin);
ma=getans(1,0,q+1,C,q+1,qmax);
if (ma.first-mi.first>=(long long)c[i]) A=C;
else B=C-1;
}
mi=getans(1,0,q+1,A,q+1,qmin);
ma=getans(1,0,q+1,A,q+1,qmax);
res=getans(1,0,q+1,q+1,q+1,qmax).first;
if (mi.second>ma.second) res=res-mi.first;
else res=c[i]-(ma.first-res);
ans.push_back((int)res);
cnt=qoff[i].size();
for (int j=0;j<cnt;j++)
update(1,0,q+1,indoff[i][j], q+1,qoff[i][j]);
}//i
return ans;
}
