#include "nile.h" #include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define pii pair <int, int> #define tiii tuple <int, 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; int lb[N], rb[N], sz[N], oddmin[N], evenmin[N], specialmin[N], par[N], mn; int dsu(int aa){ return par[aa] = (aa == par[aa] ? aa : dsu(par[aa])); } int parity(int node){ if (sz[node] % 2 == 0) return 0; if (lb[node] % 2) return min(specialmin[node], oddmin[node]); else return min(specialmin[node], evenmin[node]); } void unite(int u, int v){ if (dsu(u) == dsu(v)) return; mn -= (parity(dsu(u)) + parity(dsu(v))); lb[dsu(v)] = min(lb[dsu(v)], lb[dsu(u)]); rb[dsu(v)] = min(rb[dsu(v)], rb[dsu(u)]); sz[dsu(v)] += sz[dsu(u)]; oddmin[dsu(v)] = min(oddmin[dsu(v)], oddmin[dsu(u)]); evenmin[dsu(v)] = min(evenmin[dsu(v)], evenmin[dsu(u)]); specialmin[dsu(v)] = min(specialmin[dsu(v)], specialmin[dsu(u)]); par[dsu(u)] = dsu(v); mn += parity(dsu(v)); } 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 wei = artifactsB[j++]; int l = lower_bound(artifactsB.begin(), artifactsB.end(), wei - d) - artifactsB.begin(); int r = upper_bound(artifactsB.begin(), artifactsB.end(), wei + 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(); iota(par, par + N, 0ll); // int32_t q = (int32_t)e.size(); for (int32_t i = 0; i < n; i++) { int mnn = min(aa[i], bb[i]); sum += bb[i]; w[i + 1] = ww[i]; a[i + 1] = aa[i] - bb[i]; b[i + 1] = bb[i] - mnn; 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)); int q = e.size(); vector <int> r(q); vector <pii> que; for (int i = 0; i < q; i++) { que.emb(e[i], i); } sort(all(que)); vector <tiii> events; for (int i = 1; i < n; i++) { events.emb(artifacts[i + 1].first - artifacts[i].first, 0, i); } for (int i = 2; i < n; i++) { events.emb(artifacts[i + 1].first - artifacts[i - 1].first, 1, i); } sort(all(events)); int j = 0; for (int i = 1; i <= n; i++) { int ii = artifacts[i].second; if (i % 2) oddmin[i] = a[ii], evenmin[i] = inf; else oddmin[i] = inf, evenmin[i] = a[ii]; specialmin[i] = inf; sz[i] = 1; lb[i] = i; rb[i] = i; mn += parity(i); } for (auto [dis, type, idxx] : events) { while (j < q && que[j].first < dis) { r[que[j].second] = sum + mn; j++; } if (type == 0) { // normal merge unite(idxx, idxx + 1); } else { // special min mn -= parity(dsu(idxx)); specialmin[dsu(idxx)] = min(specialmin[dsu(idxx)], a[artifacts[idxx].second]); mn += parity(dsu(idxx)); } } while (j < q) { r[que[j].second] = sum + mn; j++; } return r; } // int32_t main() { // // Example test case input // // int N = 5; // vector<int32_t> W = {15, 12, 2, 10, 21}; // vector<int32_t> A = {5, 4, 5, 6, 3}; // vector<int32_t> B = {1, 2, 2, 3, 2}; // vector<int32_t> E = {5, 9, 1}; // vector<int> results = calculate_costs(W, A, B, E); // for (auto res : results) { // cout << res << endl; // } // return 0; // }