#include "nile.h"
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int N;
struct minseg {
ll tree[404040];
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = 1e18;
return;
}
int mid = (st+ed)/2;
init(2*v, st, mid);
init(2*v+1, mid+1, ed);
tree[v] = min(tree[2*v], tree[2*v+1]);
}
void update(int v, int st, int ed, int idx, ll val) {
if (st > idx || ed < idx) return;
if (st == idx && ed == idx) {
tree[v] = min(tree[v], val);
return;
}
int mid = (st+ed)/2;
update(2*v, st, mid, idx, val);
update(2*v+1, mid+1, ed, idx, val);
tree[v] = min(tree[2*v], tree[2*v+1]);
}
ll get(int v, int st, int ed, int lt, int rt) {
if (lt > ed || rt < st) return 1e18;
if (lt <= st && ed <= rt) return tree[v];
int mid = (st+ed)/2;
return min(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt));
}
} o1, o2, e1, e2;
vector<pll> C;
ll block(int st, int ed) { // [st, ed]
if ((ed-st)%2 == 1) return 0;
if (st%2) return min(o1.get(1, 0, N-1, st, ed), e2.get(1, 0, N-1, st, ed));
else return min(e1.get(1, 0, N-1, st, ed), o2.get(1, 0, N-1, st, ed));
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
int Q = (int)E.size();
N = (int)W.size();
ll sum = 0;
for (int i = 0; i < N; i++) sum += B[i];
vector<ll> R(Q, sum);
for (int i = 0; i < N; i++) C.push_back({W[i], A[i]-B[i]});
sort(C.begin(), C.end());
o1.init(1, 0, N-1);
e1.init(1, 0, N-1);
for (int i = 0; i < N; i++) {
if (i%2) o1.update(1, 0, N-1, i, C[i].second);
else e1.update(1, 0, N-1, i, C[i].second);
}
o2.init(1, 0, N-1);
e2.init(1, 0, N-1);
priority_queue<pll, vector<pll>, greater<pll>> two, one;
for (int i = 1; i < N-1; i++) {
two.push({C[i+1].first - C[i-1].first, i});
}
for (int i = 1; i < N; i++) {
one.push({C[i].first - C[i-1].first, i});
}
vector<ll> qry;
map<ll, ll> ans;
for (int i = 0; i < Q; i++) qry.push_back(E[i]);
sort(qry.begin(), qry.end());
qry.erase(unique(qry.begin(), qry.end()), qry.end());
map<pll, ll> blocks;
sum = 0;
for (int i = 0; i < N; i++) {
blocks[{i, i}] = C[i].second;
sum += C[i].second;
}
for (ll D : qry) {
while (!two.empty()) {
if (two.top().first > D) break;
int i = two.top().second;
if (i%2) o2.update(1, 0, N-1, i, C[i].second);
else e2.update(1, 0, N-1, i, C[i].second);
auto iter = blocks.upper_bound({i, 0}); iter--;
sum -= iter->second;
iter->second = block(iter->first.first, iter->first.second);
sum += iter->second;
two.pop();
}
while (!one.empty()) {
if (one.top().first > D) break;
int i = one.top().second;
auto now = blocks.lower_bound({i, 0});
auto prev = now; prev--;
sum -= now->second;
sum -= prev->second;
pll temp = {prev->first.first, now->first.second};
blocks[temp] = block(prev->first.first, now->first.second);
blocks.erase(prev);
blocks.erase(now);
sum += blocks[temp];
one.pop();
}
ans[D] = R[0] + sum;
}
for (int t = 0; t < Q; t++) {
R[t] = ans[E[t]];
}
return R;
}
