Contest Results

(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';
}