Explanation

If we need to move from $a$ to $b$ with a slingshot from $x$ to $y$ that takes $t$ time, then it will take $\left|a - x\right| + \left|b - y\right| + t$ time.

To eliminate the absolute values, we have to do a bit of casework. Note that the result for using a given slingshot is always in the form of $t + (\pm a \pm x) + (\pm b \pm y)$; because we are doing casework on the signs, we can separate the cost for using a slingshot from the values of $a$ and $b$.

So, we can consider each of the four cases and use a range minimum segment tree to keep track of the best slingshots for each prefix/suffix of the array. My implementation processes the four cases in two iterations, where in one iteration $a \leq x$, and in the other $a \geq x$.

Implementation

Time Complexity: $\mathcal{O}((N + Q) \log{N})$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

 Code Snippet: Segment Tree (from the module) (Click to expand)

int main() {
	freopen("slingshot.in", "r", stdin);
	freopen("slingshot.out", "w", stdout);