#include "nile.h" #include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define pii pair <int, int> #define emb emplace_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define iShowSpeed cin.tie(NULL)->sync_with_stdio(false) #define pvi pair <vector <int32_t>, int> const int N = 1e5 + 5; const int inf = 1e18; int n, w[N], a[N], b[N], alone[N], idx[N], pref[N], sum; vector <int> idxB, idB; vector <pii> artifacts(1); vector <int> artifactsB, Aprices; struct { int seg[4 * N]; void build(int l, int r, int i){ if (l == r) return seg[i] = a[l], void(); int mid = (l + r) / 2; build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1); seg[i] = min(seg[2 * i], seg[2 * i + 1]); } int query(int l, int r, int i, int ll, int rr){ if (l >= ll && r <= rr) return seg[i]; else return inf; int mid = (l + r) / 2; return min(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr)); } } segA; struct { int seg[4 * N]; void build(int l, int r, int i){ if (l == r) return seg[i] = b[l], void(); int mid = (l + r) / 2; build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1); seg[i] = min(seg[2 * i], seg[2 * i + 1]); } int query(int l, int r, int i, int ll, int rr){ if (l >= ll && r <= rr) return seg[i]; else return inf; int mid = (l + r) / 2; return min(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr)); } } segB; int solve(int d){ // cout << "D is " << d << "\n"; // int sz = idxB.size(); vector <int> left(n + 1), right(n + 1), mx(n + 1); int j = 0; for (auto i : idxB) { int w = artifactsB[j++]; int l = lower_bound(artifactsB.begin(), artifactsB.end(), w - d) - artifactsB.begin(); int r = upper_bound(artifactsB.begin(), artifactsB.end(), w + d) - artifactsB.begin() - 1; left[i] = l; right[i] = r; } j = 0; vector <pii> intervals; for (auto i : idxB) { // int ii = artifacts[i].second; // cout << i << ": idx is " << ii << ": weight is " << artifactsB[j++] << ": bounds are " << left[i] << ", " << right[i] << ": there are " << right[i] - left[i] + 1 << " in the range" << "\n"; if (intervals.empty() || left[i] > intervals.back().second) intervals.emb(left[i], right[i]); else intervals.back().second = max(intervals.back().second, right[i]); } int ans = sum; for (auto [l, r] : intervals) { // cout << "[" << l << ", " << r << "]\n"; if ((r - l + 1) % 2 == 0) continue; int cur = inf; for (int i = l; i <= r; i++) { if ((i - l) % 2 == 0) cur = min(cur, Aprices[i]); else if (i != l && i != r && artifactsB[i + 1] - artifactsB[i - 1] <= d) cur = min(cur, Aprices[i]); } ans += cur; } // cout << "--------------------------------------------------------------\n"; return ans; } vector <int> calculate_costs(vector<int32_t> ww, vector<int32_t> aa, vector<int32_t> bb, vector<int32_t> e) { n = ww.size(); // int32_t q = (int32_t)e.size(); for (int32_t i = 0; i < n; i++) { int mn = min(aa[i], bb[i]); sum += mn; w[i + 1] = ww[i]; a[i + 1] = aa[i] - mn; b[i + 1] = bb[i] - mn; if (a[i + 1] == 0) a[i + 1] = inf; if (b[i + 1] == 0) b[i + 1] = inf; if (a[i + 1] == inf) alone[i + 1] = 1; artifacts.emb(ww[i], i + 1); } sort(all(artifacts)); for (int i = 1; i <= n; i++) { idx[i] = artifacts[i].second; if (!alone[idx[i]]) idxB.emb(i), artifactsB.emb(artifacts[i].first), Aprices.emb(a[idx[i]]); } segA.build(1, n, 1); segB.build(1, n, 1); for (auto e : idxB) pref[e]++; for (int i = 1; i <= n; i++) pref[i] += pref[i - 1]; vector <int> r; for (auto i : e) { r.emb(solve(i)); } return r; }