#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pi = pair<int, int>;
using vpi = vector<pi>;
#define sz(x) int((x).size())
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define srt(x) sort(all(x))
#define rev(x) reverse(all(x))
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define trace(x) for (auto &el : x) cout << el << " "
#define each(a, x) for (auto &a : x)
const ll INF = 1e18;
struct Node {
ll best; int idx;
Node() : best(INF), idx(-1) {};
Node(ll v, int i) : best(v), idx(i) {};
Node(Node left, Node right) {
best = min(left.best, right.best);
if (left.best < right.best) idx = left.idx;
else idx = right.idx;
}
};
struct RMQ {
int n; vl arr; vector<Node> st;
vl lazy;
RMQ() {};
RMQ(int N, vl Arr) {
n = N; arr = Arr;
st.resize(4*n);
lazy.assign(4*n, 0);
build(0, 0, n);
}
Node build(int i, int l, int r) {
if (l + 1 == r) return st[i] = Node(arr[l], l);
int m = l + (r - l) / 2;
return st[i] = Node(build(2*i+1, l, m), build(2*i+2, m, r));
}
void apply(int i, ll update) {
lazy[i] += update;
st[i].best += update;
}
void push_down(int i) {
apply(2*i+1, lazy[i]);
apply(2*i+2, lazy[i]);
lazy[i] = 0;
}
Node query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return Node();
if (ql <= l && r <= qr) return st[i];
push_down(i);
int m = l + (r - l) / 2;
return Node(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
Node update(int i, int l, int r, int ql, int qr, ll v) {
if (r <= ql || qr <= l) return st[i];
if (ql <= l && r <= qr) {
apply(i, v);
return st[i];
}
push_down(i);
int m = l + (r - l) / 2;
return st[i] = Node(update(2*i+1, l, m, ql, qr, v), update(2*i+2, m, r, ql, qr, v));
}
Node query(int l, int r) {
return query(0, 0, n, l, r);
}
void update(int k, ll v) {
update(0, 0, n, k, k+1, v);
}
void update(int l, int r, ll v) {
update(0, 0, n, l, r, v);
}
};
struct DSU {
int n;
vector<int> par, size;
DSU(int N) {
n = N; par.assign(n, 0); iota(par.begin(), par.end(), 0); size.assign(n, 1);
}
int find(int v) {
if (par[v] == v) return v;
return par[v] = find(par[v]);
}
void unite(int a, int b, ll &pairs) {
a = find(a), b = find(b);
if (a != b) {
if (size[a] < size[b]) swap(a, b);
pairs -= (size[a] / 2) + (size[b] / 2);
par[b] = a; size[a] += size[b];
pairs += size[a] / 2;
}
}
};
void super_brute(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
FOR(qn, 0, q) {
vi perm(n); iota(all(perm), 0);
ll best = INF;
vi best_perm;
do {
ll cur = 0;
bool is_b = true;
for (int i = 0; i < n; i++) {
if (is_b && i < n - 1 && abs(w[perm[i]] - w[perm[i+1]]) <= e[qn]) {
cur += b[perm[i]] + b[perm[i+1]];
i++;
} else {
is_b = false;
cur += a[perm[i]];
}
}
if (cur < best) {
best = cur;
best_perm = perm;
}
} while (next_permutation(all(perm)));
answers[qn] = best;
cout << "E[i]: " << e[qn] << " answers[qn]: " << answers[qn] << "\n";
trace(best_perm); cout << "\n";
}
}
void ab12(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
vpi edges; FOR(i, 0, n-1) edges.pb({w[i+1] - w[i], i}); srt(edges);
auto dsu = DSU(n);
ll pairs = 0;
int cur_edge = 0;
FOR(qn, 0, q) {
while (cur_edge < edges.size() && edges[cur_edge].first <= e[qn]) {
pi edge = edges[cur_edge];
ll weight = edge.first;
int u = edge.second, v = edge.second + 1;
dsu.unite(u, v, pairs);
cur_edge++;
}
answers[qn] = 2 * n - 2 * pairs;
}
}
void linedup(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
FOR(qn, 0, q) {
answers[qn] = accumulate(all(b), 0LL);
vl ab(n); FOR(i, 0, n) ab[i] = a[i] - b[i];
auto rmq = RMQ(n, ab);
if (n % 2 == 1 && e[qn] == 1) {
vl DP(n+1, INF);
DP[0] = 0;
FOR(i, 0, n) {
DP[i+1] = min(DP[i+1], DP[i] + a[i]);
if (i > 0) {
DP[i+1] = min(DP[i+1], DP[i-1] + b[i-1] + b[i]);
}
}
answers[qn] = DP[n];
} else if (n%2==1) {
answers[qn] += rmq.query(0, n).best;
}
}
}
void weirdp(int n, int q, vl &a, vl &b, vl &w, vl &e, vl &answers) {
FOR(qn, 0, q) {
ll best = INF;
vl DP(n+1, INF);
DP[0] = 0;
auto rmq = RMQ(n, vl(n, INF));
FOR(i, 0, n) {
DP[i+1] = DP[i] + a[i];
int pos = ub(bg(w), bg(w) + i, w[i] - e[qn] - 1) - bg(w);
ll qbest = b[i] + rmq.query(pos, i).best;
DP[i+1] = min(DP[i+1], qbest);
rmq.update(0, i, a[i]);
rmq.update(i, (DP[i] + b[i]) - rmq.query(i, i+1).best);
}
best = DP.back();
answers[qn] = best;
}
}
vl calculate_costs(vi W, vi A, vi B, vi E) {
int n = sz(W), q = sz(E);
vl w(all(W)), a(all(A)), b(all(B)), e(all(E)); srt(e);
vi indices(n); iota(all(indices), 0); sort(all(indices), [&](int i, int j) {return w[i] < w[j];});
FOR(i, 0, n) w[i] = W[indices[i]], a[i] = A[indices[i]], b[i] = B[indices[i]];
vl answers(q, 0);
// super_brute(n, q, a, b, w, e, answers);
ab12(n, q, a, b, w, e, answers);
// linedup(n, q, a, b, w, e, answers);
// weirdp(n, q, a, b, w, e, answers);
vl R(q, 0); FOR(i, 0, q) R[i] = answers[lb(all(e), E[i]) - bg(e)];
return R;
}
