(Analysis by Dhruv Rohatgi )

Let us formalize the problem. We are given $N$ slingshots, where slingshot $i$ has parameters $(x_i, y_i, t_i)$; we are also $M$ queries. Query $j$ has parameters $(a_i, b_i)$, and we are asked to determine

$$\min_i |a_j - x_i| + |b_j - y_i| + t_i.$$
Here we are ignoring the case where a pile may be transported without using any slingshots at all, but it is easy to check this case in a single final pass through the queries. So from here on, we assume that exactly one slingshot must be used in each query, and as a result we obtain the above expression.

Fix some query $j$. There are four cases for the location of the best slingshot $i$. It may satisfy:

• $a_j > x_i$ and $b_j > y_i$,
• $a_j \leq x_i$ and $b_j > y_i$,
• $a_j > x_i$ and $b_j \leq y_i$, or
• $a_j \leq x_i$ and $b_j \leq y_i$.

Each case corresponds to a "quadrant" relative to the query. If we can find, for each quadrant, the minimum cost of query $j$ if we use a slingshot in that quadrant, then the answer for query $j$ is simply the minimum of the four quadrant-specific minima.

Consider some slingshot $i$ which falls into the first case, for query $j$. Then the cost of using slingshot $i$ for query $j$ is

$$a_j + b_j + t_i - x_i - y_i.$$
Therefore the first-quadrant minimum for query $j$ is
$$a_j + b_j + \min_i (t_i - x_i - y_i),$$
where $i$ ranges over all slingshots satisfying $a_j > x_i$ and $b_j > y_i$.

To compute this quantity for all queries, sweep left-to-right. Then when a query is encountered, we wish to find the minimum $t_i - x_i - y_i$ over all slingshots which have been encountered already and satisfy $b_j > y_i$. Such queries can be answered efficiently by maintaining a segment tree; whenever a slingshot is encountered by the sweepline, the value $t_i - x_i - y_i$ is inserted with index $y_i$. Then the desired minimum can be obtained by a range minimum query.

The other three cases are analogous. Note that the coordinates $y_i$ must be compressed so that they can be used as indices into the segment tree.

Overall time complexity is $O((N+M) \log (N+M))$.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define SEG (1<<18)
#define INF 1000000000000000LL

int N,Q;
long long x[MAXN], y[MAXN], t[MAXN];
int cx[MAXN],cy[MAXN];
int cid[MAXN];

long long qx[MAXN],qy[MAXN],qt[MAXN];
int qcx[MAXN],qcy[MAXN];
int qid[MAXN];

class SegTree
{
public:
long long seg[2*SEG];
int l[2*SEG],r[2*SEG];
int low,high;

void init()
{
for(int i=SEG;i<2*SEG;i++)
{
seg[i] = -INF;
l[i] = r[i] = i-SEG;
}
for(int i=SEG-1;i>0;i--)
{
seg[i] = -INF;
l[i] = l[2*i], r[i] = r[2*i+1];
}
}
void update(int i,long long v)
{
i += SEG;
for(;i>0;i/=2)
seg[i] = max(seg[i],v);
}
long long getMax(int i)
{
if((l[i]>high)||(r[i]<low)) return -INF;
if((l[i]>=low)&&(r[i]<=high)) return seg[i];
return max(getMax(2*i),getMax(2*i+1));
}
};

bool cmp(int a,int b)
{
return x[a]<x[b];
}

bool qcmp(int a,int b)
{
return qx[a]<qx[b];
}

long long ansLeft[MAXN];
long long ansRight[MAXN];

int main()
{
cin >> N >> Q;
vector<long long> vx,vy;
for(int i=0;i<N;i++)
{
cin >> x[i] >> y[i] >> t[i];
vx.push_back(x[i]);
vy.push_back(y[i]);
cid[i] = i;
}
sort(cid,cid+N,cmp);
for(int i=0;i<Q;i++)
{
cin >> qx[i] >> qy[i];
vx.push_back(qx[i]);
vy.push_back(qy[i]);
qid[i] = i;
}
sort(qid,qid+Q,qcmp);

sort(vx.begin(),vx.end());
sort(vy.begin(),vy.end());
vx.resize(distance(vx.begin(),unique(vx.begin(),vx.end())));
vy.resize(distance(vy.begin(),unique(vy.begin(),vy.end())));
for(int i=0;i<N;i++)
{
cx[i] = lower_bound(vx.begin(),vx.end(),x[i]) - vx.begin();
cy[i] = lower_bound(vy.begin(),vy.end(),y[i]) - vy.begin();
}
for(int i=0;i<Q;i++)
{
qcx[i] = lower_bound(vx.begin(),vx.end(),qx[i]) - vx.begin();
qcy[i] = lower_bound(vy.begin(),vy.end(),qy[i]) - vy.begin();
}

SegTree up, down;
up.init();
down.init();
int j = 0;
for(int i=0;i<Q;i++)
{
int cur = qid[i];
while(j < N && x[cid[j]] <= qx[cur])
{
down.update(cy[cid[j]], x[cid[j]]+y[cid[j]]-t[cid[j]]);
up.update(cy[cid[j]], x[cid[j]]-y[cid[j]]-t[cid[j]]);
j++;
}
down.low = 0, down.high = qcy[cur];
up.low = qcy[cur], up.high = vy.size()-1;
ansLeft[cur] = min(qx[cur] + qy[cur] - down.getMax(1), qx[cur] - qy[cur] - up.getMax(1));
}
up.init();
down.init();
j = N-1;
for(int i=Q-1;i>=0;i--)
{
int cur = qid[i];
while(j>=0 && x[cid[j]] >= qx[cur])
{
down.update(cy[cid[j]], -x[cid[j]]+y[cid[j]]-t[cid[j]]);
up.update(cy[cid[j]], -x[cid[j]]-y[cid[j]]-t[cid[j]]);
j--;
}
down.low = 0, down.high = qcy[cur];
up.low = qcy[cur], up.high = vy.size()-1;
ansRight[cur] = min(-qx[cur] + qy[cur] - down.getMax(1), -qx[cur] - qy[cur] - up.getMax(1));
}
for(int i=0;i<Q;i++)
cout << min(min(ansLeft[i],ansRight[i]),(long long)abs(qx[i]-qy[i])) << '\n';
}