#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); }