#include "nile.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cassert>
#include <climits>
#include <set>
#include <tuple>
using namespace std;
using ll = long long;
bool debug = false;
struct Input {
vector<int>& W; vector<int>& A;
vector<int>& B; vector<int>& E;
};
namespace Subtask7 {
ll ID_MIN = LLONG_MAX;
struct Item {
int W, A, B;
};
class IntervalItemSet {
int n = 0;
vector<Item>& items;
ll totalCost = 0;
struct IntervalItem {
int s, e;
ll sumB = 0;
ll evenIdxMinP = 0, oddIdxMinP = 0, passingIdxMinP = 0;
ll cost = 0;
int size() const { return e - s + 1; }
ll renewCost() {
if (size() % 2 == 0)
cost = sumB;
else
cost = sumB + min(evenIdxMinP, passingIdxMinP);
return cost;
}
ll getCost() const { return cost; }
bool operator<(const IntervalItem& o) const {
return pair{s, e} < pair{o.s, o.e};
}
};
set<IntervalItem> intervalSet;
set<IntervalItem>::iterator getIntervalIt(int i) {
auto it = intervalSet.upper_bound(IntervalItem{i, n});
assert(it != intervalSet.begin());
--it;
return it;
}
void insert(const IntervalItem& iit) {
auto [it, inserted] = intervalSet.insert(iit);
assert(inserted);
totalCost += it->getCost();
}
void erase(set<IntervalItem>::iterator it) {
totalCost -= it->getCost();
intervalSet.erase(it);
}
public:
IntervalItemSet() = default;
explicit IntervalItemSet(vector<Item>& items_) : items(items_), totalCost(0) {
n = (int)items.size();
for (int i = 0; i < n; ++i) {
IntervalItem iit{i, i};
iit.sumB = items[i].B;
iit.evenIdxMinP = items[i].A - items[i].B;
iit.oddIdxMinP = ID_MIN;
iit.passingIdxMinP = ID_MIN;
iit.renewCost();
insert(iit);
}
}
ll getTotalCost() const { return totalCost; }
IntervalItem getUnionedInterval(IntervalItem aInterval, IntervalItem bInterval) {
assert(aInterval.s != bInterval.s);
if (aInterval.s > bInterval.s) swap(aInterval, bInterval);
assert(aInterval.e + 1 == bInterval.s);
IntervalItem unioned{aInterval.s, bInterval.e};
unioned.sumB = aInterval.sumB + bInterval.sumB;
if (aInterval.size() % 2 == 0) {
unioned.evenIdxMinP = min(aInterval.evenIdxMinP, bInterval.evenIdxMinP);
unioned.oddIdxMinP = min(aInterval.oddIdxMinP, bInterval.oddIdxMinP);
unioned.passingIdxMinP = min(aInterval.passingIdxMinP, bInterval.passingIdxMinP);
}
else {
unioned.evenIdxMinP = min(aInterval.evenIdxMinP, bInterval.oddIdxMinP);
unioned.oddIdxMinP = min(aInterval.oddIdxMinP, bInterval.evenIdxMinP);
unioned.passingIdxMinP = min(aInterval.passingIdxMinP, bInterval.passingIdxMinP);
}
unioned.renewCost();
return unioned;
}
bool unionInterval(int a, int b) {
auto aIntervalIt = getIntervalIt(a);
auto bIntervalIt = getIntervalIt(b);
if (aIntervalIt == bIntervalIt) {
if (a > b) swap(a, b);
// if (debug) assert(a + 2 == b);
assert(a + 2 == b);
// auto& minP = aIntervalIt->passingIdxMinP;
// minP = min(minP, (ll)items[a+1].A - items[a+1].B);
IntervalItem unioned = *aIntervalIt;
erase(aIntervalIt);
if (debug) printf("(a, b) = (%d, %d)\n", a, b);
unioned.passingIdxMinP = min(unioned.passingIdxMinP, (ll)items[a+1].A - items[a+1].B);
unioned.renewCost();
insert(unioned);
return false;
}
else {
IntervalItem aInterval = *aIntervalIt;
IntervalItem bInterval = *bIntervalIt;
erase(aIntervalIt);
erase(bIntervalIt);
IntervalItem unioned = getUnionedInterval(aInterval, bInterval);
insert(unioned);
return true;
}
}
};
vector<Item> makeItems(vector<int>& W, vector<int>& A, vector<int>& B) {
int n = (int)W.size();
vector<Item> items(n);
for (int i = 0; i < n; ++i) {
items[i] = Item{W[i], A[i], B[i]};
}
return items;
}
struct Edge {
int a, b;
int d;
};
vector<pair<int, int>> makeDIdxPairs(const vector<int>& E) {
vector<pair<int, int>> DIdxPairs;
DIdxPairs.reserve(E.size());
for (int i = 0; i < (int)E.size(); ++i) {
DIdxPairs.emplace_back(E[i], i);
}
return DIdxPairs;
}
vector<ll> solve(vector<int>& W, vector<int>& A,
vector<int>& B, vector<int>& E)
{
int Q = (int)E.size();
int n = (int)W.size();
// 1. sort (E, index) pairs by E
vector<pair<int, int>> DIdxPairs = makeDIdxPairs(E);
sort(DIdxPairs.begin(), DIdxPairs.end());
// 2. make items sorted by W
vector<Item> items = makeItems(W, A, B);
sort(items.begin(), items.end(),
[](const Item& a, const Item& b) {
return a.W < b.W;
});
// 3. make edges
vector<Edge> edges;
for (int i = 0; i < n-1; ++i) {
edges.push_back({i, i + 1, items[i+1].W - items[i].W});
}
for (int i = 0; i < n-2; ++i) {
edges.push_back({i, i + 2, items[i+2].W - items[i].W});
}
sort(edges.begin(), edges.end(),
[](const Edge& e1, const Edge& e2) {
return tuple{e1.d, e1.b - e1.a} < tuple{e2.d, e2.b - e2.a};
});
vector<ll> R(Q, 0);
IntervalItemSet iits(items);
int i = 0, j = 0;
while (i < (int)edges.size()) {
Edge curEdge = edges[i];
int d = curEdge.d;
while (j < Q) {
auto [D, idx] = DIdxPairs[j];
if (!(D < d)) break;
R[idx] = iits.getTotalCost();
++j;
}
if (j >= Q) break;
while (i < (int)edges.size() && edges[i].d == d) {
iits.unionInterval(edges[i].a, edges[i].b);
++i;
}
}
while (j < Q) {
auto [_, idx] = DIdxPairs[j];
R[idx] = iits.getTotalCost();
++j;
}
return R;
}
inline vector<ll> solve(const Input& in) {
return solve(in.W, in.A, in.B, in.E);
}
}
vector<ll> calculate_costs( vector<int> W, vector<int> A,
vector<int> B, vector<int> E)
{
int Q = (int)E.size();
Input in{W, A, B, E};
return Subtask7::solve(in);
}
