cpp ``` #include #include #include #include using namespace std; vector minimum_delivery_costs(vector& delivery_charges, vector>& queries) { int n = delivery_charges.size(); // Step 1: Create a sorted array of (value, original index) vector> sorted; for (int i = 0; i < n; ++i) { sorted.emplace_back(delivery_charges[i], i); } sort(sorted.begin(), sorted.end()); // Step 2: Map original indices to their positions in the sorted array vector pos(n); for (int i = 0; i < n; ++i) { pos[sorted[i].second] = i; } // Step 3: Compute forward and backward edge costs vector forward_cost(n - 1); vector backward_cost(n - 1); for (int k = 0; k < n - 1; ++k) { long long right_diff = static_cast(sorted[k + 1].first) - sorted[k].first; if (k == 0) { forward_cost[k] = 1; // Only right neighbor exists } else { long long left_diff = static_cast(sorted[k].first) - sorted[k - 1].first; forward_cost[k] = (right_diff < left_diff) ? 1 : right_diff; } } for (int k = 0; k < n - 1; ++k) { long long left_diff = static_cast(sorted[k + 1].first) - sorted[k].first; if (k + 1 == n - 1) { backward_cost[k] = 1; // Only left neighbor exists } else { long long right_diff = static_cast(sorted[k + 2].first) - sorted[k + 1].first; backward_cost[k] = (left_diff < right_diff) ? 1 : left_diff; } } // Step 4: Compute prefix sums for forward and backward paths vector prefix_forward(n, 0); for (int i = 1; i < n; ++i) { prefix_forward[i] = prefix_forward[i - 1] + forward_cost[i - 1]; } vector prefix_backward(n, 0); for (int i = n - 2; i >= 0; --i) { prefix_backward[i] = prefix_backward[i + 1] + backward_cost[i]; } // Step 5: Answer each query vector results; for (const auto& query : queries) { int start = query[0]; int end = query[1]; int i = pos[start]; int j = pos[end]; if (i <= j) { results.push_back(prefix_forward[j] - prefix_forward[i]); } else { results.push_back(prefix_backward[j] - prefix_backward[i]); } } return results; } // Time Complexity: O(n log n + q) // Space Complexity: O(n + q) ```

Quick Overview

Minimum Delivery Cost Between Cities