#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> big0(500001,-1e18);
vector<long long> big1(500001,-1e18);
vector<long long> seg0(500001,-1e18);
vector<long long> seg1(500001,-1e18);
vector<long long> haha(500001);
vector<long long> pr(500001);
long long n;
void build(long long l, long long r, long long x) {
if(l == r) {
if(l%2) {
big1[x] = haha[l];
}
else {
big0[x] = haha[l];
}
return;
}
long long mid = (l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
big0[x] = max(big0[x*2],big0[x*2+1]);
big1[x] = max(big1[x*2],big1[x*2+1]);
}
void upd(long long l, long long r, long long x, long long p, long long br) {
if(l == r) {
if(l%2) {
seg1[x] = br;
}
else {
seg0[x] = br;
}
return;
}
long long mid = (l+r)/2;
if(p <= mid) {
upd(l,mid,x*2,p,br);
}
else {
upd(mid+1,r,x*2+1,p,br);
}
seg0[x] = max(seg0[x*2],seg0[x*2+1]);
seg1[x] = max(seg1[x*2],seg1[x*2+1]);
}
long long calc(long long l, long long r, long long ql, long long qr, long long x, bool y, bool z) {
if(qr < ql) {
return -1e18;
}
if(l == ql && r == qr) {
if(y) {
if(z) {
return big1[x];
}
else {
return big0[x];
}
}
else {
if(z) {
return seg1[x];
}
else {
return seg0[x];
}
}
}
long long mid = (l+r)/2;
if(qr <= mid) {
return calc(l,mid,ql,qr,x*2,y,z);
}
else if(ql > mid) {
return calc(mid+1,r,ql,qr,x*2+1,y,z);
}
else {
return max(calc(l,mid,ql,mid,x*2,y,z),calc(mid+1,r,mid+1,qr,x*2+1,y,z));
}
}
long long dude(long long l, long long r) {
if(r < l) {
return 0;
}
long long ans = pr[r]-pr[l-1];
long long c = max(calc(1,n,l,r,1,1,l%2),calc(1,n,l,r,1,0,(l+1)%2));
if((r-l+1)%2 == 0) {
c = 0;
}
return ans-c;
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> e) {
vector<pair<long long,long long>> wut(1,{0,0});
n = w.size();
for(long long i = 0; i < w.size(); i++) {
wut.push_back({w[i],i});
}
sort(wut.begin(),wut.end());
for(long long i = 1; i <= n; i++) {
haha[i] = b[wut[i].second]-a[wut[i].second];
pr[i] = b[wut[i].second]+pr[i-1];
}
build(1,n,1);
vector<long long> ans(e.size());
vector<pair<long long,long long>> no(0);
for(long long i = 0; i < e.size(); i++) {
no.push_back({e[i],i});
}
sort(no.begin(),no.end());
long long sb = 0;
for(long long i = 0; i < a.size(); i++) {
sb+=a[i];
}
vector<pair<long long,pair<long long,long long>>> wow(0);
for(long long i = 2; i <= n; i++) {
wow.push_back({wut[i].first-wut[i-1].first,{0,i-1}});
if(i > 2) {
wow.push_back({wut[i].first-wut[i-2].first,{1,i-2}});
}
}
upd(1,n,1,1,haha[1]);
upd(1,n,1,n,haha[n]);
sort(wow.begin(),wow.end());
set<long long> idk;
for(long long i = 0; i <= w.size(); i++) {
idk.insert(i);
}
long long y = 0;
for(long long i = 0; i < wow.size(); i++) {
while(y < no.size() && no[y].first < wow[i].first) {
ans[no[y].second] = sb;
y++;
}
long long p = wow[i].second.second;
if(wow[i].second.first) {
p++;
long long l = *(--idk.upper_bound(p)),r = *idk.lower_bound(p);
sb-=dude(l+1,r);
upd(1,n,1,p,b[wut[p].second]-a[wut[p].second]);
sb+=dude(l+1,r);
}
else {
idk.erase(p);
long long l = *(--idk.upper_bound(p)),r = *idk.lower_bound(p);
sb-=dude(l+1,p);
sb-=dude(p+1,r);
sb+=dude(l+1,r);
}
}
for(long long i = y; i < no.size(); i++) {
ans[no[i].second] = sb;
}
return ans;
}
