// correct/solution-subtask4.cpp
#include "deliveries.h"
#include <iostream>
#include <vector>
#define MAXN 101000
using namespace std;
long long N, centroid, allSumW, ans, uValue, uFrom, flippedWT, allSumTxW;
long long W[MAXN];
long long sumW[MAXN];
long long T[MAXN];
long long sumT[MAXN];
struct node{
int a, b;
long long w, sumWT, sumL, sumT;
node* leftC;
node* rightC;
};
node* tree;
node* build(int x, int y){
node* p = new node;
node* lc = nullptr;
node* rc = nullptr;
p->a = x; p->b = y; p->w = 0;
p->sumWT = 0; p->sumL = 0; p->sumT = 0;
if(x==y){
p->w = W[x-1];
p->sumWT = T[x-1] * sumW[x-1];
p->sumT = T[x-1];
} else {
lc = build(x,(x+y)/2);
rc = build((x+y)/2+1,y);
p->w = lc->w + rc->w;
p->sumWT = lc->sumWT + rc->sumWT;
p->sumT = lc->sumT + rc->sumT;
}
p->leftC = lc; p->rightC = rc;
return p;
}
long long sumValue(node* p){
return p->sumWT + p->sumL * p->sumT;
}
void push_down(node* p){
(p->leftC)->sumL += p->sumL;
(p->rightC)->sumL += p->sumL;
p->sumL = 0;
}
void update_node(node* p){
p->sumWT = sumValue(p->leftC) + sumValue(p->rightC);
}
void update(node* p){
p->w += uValue;
if(p->a==p->b){
p->sumL += uValue;
return;
}
push_down(p);
if(uFrom<=(p->a+p->b)/2){
update(p->leftC);
} else {
(p->leftC)->sumL += uValue;
update(p->rightC);
}
update_node(p);
}
int findCentroid(node* p){
if(p->a==p->b){
flippedWT += sumValue(p);
return p->a-1;
}
push_down(p);
update_node(p);
if((p->rightC)->w >= uValue){
flippedWT += sumValue(p->leftC);
return findCentroid(p->rightC);
}
uValue -= (p->rightC)->w;
return findCentroid(p->leftC);
}
void init(int NN, std::vector<int> /*UU*/, std::vector<int> /*VV*/, std::vector<int> TT, std::vector<int> WW){
N = NN;
for(int i=0; i<N-1; i++){
T[i+1] = TT[i];
sumT[i+1] = sumT[i] + T[i+1];
}
for(int i=0; i<N; i++){
W[i] = WW[i];
}
W[0]++;
for(int i=0; i<N; i++){
allSumTxW += W[i] * sumT[i];
}
for(int i=N-1; i>=0; i--)
sumW[i] = sumW[i+1] + W[i];
allSumW = sumW[0];
tree = build(1,N);
}
long long max_time(int S, int X){
if(S==0) X++;
long long diff = X - W[S];
allSumTxW += diff * sumT[S];
allSumW -= W[S];
W[S] = X;
allSumW += W[S];
uFrom = S+1; uValue = diff; update(tree);
uValue = (allSumW + 1)/2; flippedWT = 0;
int cent = findCentroid(tree);
return 2 * (allSumTxW + allSumW * sumT[cent] - 2 * flippedWT);
}
