#include <bits/stdc++.h> using namespace std; #define ll long long const ll mmod = 998244353; #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> void buildls(ll l, ll r, ll i, vl& tree, ll p, vl& vals){ if (l == r && l < vals.size() && l%2 == p){ tree[i] = vals[l]; return; } else if (l == r){return;} ll mid = (l+r)/2; buildls(l, mid, 2*i, tree, p, vals); buildls(mid +1, r, 2*i+1, tree, p, vals); tree[i] = min(tree[2*i], tree[2*i+1]); return; } void buildg(ll l, ll r, ll i, vl& tree, vl& vals){ if (l == r && l < vals.size()){ tree[i] = vals[l]; return; } else if (l == r){return;} ll mid = (l+r)/2; buildg(l, mid, 2*i, tree, vals); buildg(mid +1, r, 2*i+1, tree, vals); tree[i] = min(tree[2*i], tree[2*i+1]); return; } void update(ll l, ll r, vl& tree, ll i, ll c, ll pos){ if (l == r && l == pos){ tree[i] = c; return; } if (r < pos || l > pos){ return; } ll mid = (l+r)/2; update(l, mid, tree, 2*i, c, pos); update(mid+1,r,tree,2*i+1, c, pos); tree[i] = min(tree[2*i], tree[2*i+1]); return; } ll query(ll l, ll r, ll L, ll R, ll i, vl& tree){ if (L <= l && r <= R){ return tree[i]; } if (r < L || R < l){ return 1e10; } ll mid = (l+r)/2; ll a = query(l, mid, L, R, 2*i, tree); ll b = query(mid+1, r, L, R, 2*i+1, tree); return min(a,b); } std::vector<long long> calculate_costs( std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E){ ll n = W.size(); vll nums; for (ll i = 0; i < n; i++){ nums.push_back({W[i], A[i], B[i]}); } sort(nums.begin(), nums.end()); vector<pl> queries; for (ll i = 0; i < E.size(); i++){ queries.push_back({E[i], i}); } sort(queries.begin(), queries.end()); reverse(queries.begin(), queries.end()); // Intervals set<ll> b; b.insert(0); vector<pl> intervals (n, {-1,0}); // Events vector<pl> gaps; for (ll i = 0; i < n-1; i++){ gaps.push_back({nums[i+1][0]-nums[i][0], i}); } sort(gaps.begin(), gaps.end()); reverse(gaps.begin(), gaps.end()); gaps.push_back({-1,0}); vector<pl> spojky; for (ll i = 1; i < n-1; i++){ spojky.push_back({nums[i+1][0]-nums[i-1][0], i}); } sort(spojky.begin(), spojky.end()); reverse(spojky.begin(), spojky.end()); spojky.push_back({-1,0}); // Precalc vl dif(n); for (ll i = 0; i < n; i++){dif[i] = nums[i][1]-nums[i][2];} // Tree handeling vl treel (4*n+4, 1e18); vl trees (4*n + 4, 1e18); vl treeg (4*n+4, 1e18); ll N = 1; while (N < n){ N *= 2;} buildls(0,N-1,1,treel,1, dif);//parity buildls(0,N-1,1,trees,0, dif); buildg(0,N-1,1,treeg, dif); vl prefix (n+1,0); for (ll i = 0; i < n; i++){ prefix[i+1] = prefix[i] + nums[i][2]; } ll suma = prefix[n] - prefix[0] + query(0,N-1,0,n-1,1,treeg); // (i, j) = [j+1] - [i] intervals[0] = {n-1, suma}; vl ans(queries.size(), 0); // interval calc auto intcalc = [&](ll zacatek, ll konec) { ll sub = prefix[konec+1]-prefix[zacatek]; if ((konec - zacatek)%2 == 0){ // odd length is a problem, but bounds are including ll a, b; b = 1e10; if (zacatek % 2 == 0){ a = query(0, N-1, zacatek, konec, 1, trees); } else{ a = query(0, N-1, zacatek, konec, 1, treel); } if (zacatek + 1 <= konec - 1){ b = query(0, N-1, zacatek+1, konec-1, 1, treeg); } sub += min(a,b); } return sub; }; // main algorithm ll p1 = 0; ll p2 = 0; for (ll i = 0; i < queries.size(); i++){ // Handle updates of spojky deleting, interval destruction, by gaps ll k = queries[i].first; while (spojky[p1].first > k || gaps[p2].first > k){ if (spojky[p1].first >= gaps[p2].first){ //Recalc interval where spojka is ll pos = spojky[p1].second; update(0, N-1, treeg, 1, 1e18, pos); ll start = *prev(b.upper_bound(pos)); ll end = intervals[start].first; suma -= intervals[start].second; ll sub = intcalc(start, end); suma += sub; intervals[start].second = sub; p1++; } else{ ll end1 = gaps[p2].second; //position of last element of first interval ll start1 = *prev(b.upper_bound(end1)); ll end2 = intervals[start1].first; ll start2 = end1 + 1; suma -= intervals[start1].second; ll sub = intcalc(start1, end1); intervals[start1] = {end1, sub}; suma += sub; sub = intcalc(start2, end2); intervals[start2] = {end2, sub}; b.insert(start2); suma += sub; p2++; } } ans[queries[i].second] = suma; } return ans; } /*/int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vector<int> W, A, B, E; W = {15, 12, 2, 10, 21}; A = {5, 4, 5, 6, 3}; B = {1, 2, 2, 3, 2}; E = {5, 9, 1}; vl x = calculate_costs(W, A, B, E); for (auto p : x){ cout << p << "\n"; } return 0; }/*/