jzxx3035【USACO】A Pie for a Pie

题目描述
Bessie and Elsie have each baked NN pies (1≤N≤1051≤N≤105). Each of the 2N2N pies has a tastiness value according to Bessie and a (possibly different) tastiness value according to Elsie.
Bessie is thinking about giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she will feel obligated to give one of her pies to Bessie. So as to not appear stingy nor flamboyant, Elsie will try to pick a pie that is at least as tasty (in Elsie’s eyes) as the pie she received, but no more than DD units tastier (0≤D≤1090≤D≤109). Such a pie may not exist, in which case Elsie will adopt a pseudonym and exile herself to Japan.
But if Elsie does give Bessie a pie in return, Bessie will similarly try to give Elsie a pie which is at least as tasty but no more than DD units tastier (in Bessie’s eyes) as the pie Elsie just gave her. Should this be impossible, Bessie too will exile herself. Otherwise she will give her chosen pie to Elsie. This cycle will continue until one of the cows is exiled, an unhappy outcome, or one of the cows receives a pie which she accords a tastiness value of 00, in which case the gift exchange will end and both cows will be happy.
Note that a pie may not be gifted twice, nor can either cow return a pie gifted to her.
For each of the NN pies Bessie could select as her initial gift to Elsie, determine the minimum number of pies that could possibly be gifted in the resulting exchange before the cows are happy.

输入
The first line contains the two integers NN and DD.
The next 2N2N lines contain two space-separated integers each, respectively denoting the value of a particular pie according to Bessie, and the value of that pie according to Elsie.

The first NN lines refer to Bessie’s pies, and the remaining NN lines refer to Elsie’s pies.

It is guaranteed that all tastiness values are in the range [0,109][0,109].

输出
There should be NN lines in the output. Line ii should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange started with Bessie’s pie ii. If no gift exchange starting with pie ii is happy, then line ii should contain the single integer −1−1 instead.

样例输入
2 1
1 1
5 0
4 2
1 4

样例输出
3
1

来源/分类
USACO 2017 December Gold

传送门

满分代码：
#pragma GCC optimize ("O2")
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
#define MAXN 100000
#define INF 1000000000
int N,D;
int A[2*MAXN];
int B[2*MAXN];
int dist[2*MAXN];
struct cmpA {
	bool operator()(int a,int b) const {
		return B[a]<B[b];
	}
};
struct cmpB {
	bool operator()(int a,int b) const {
		return A[a]<A[b];
	}
};
multiset<int,cmpA> sA;
multiset<int,cmpB> sB;
int que[2*MAXN];
int cur,len;
int main() {
	ios::sync_with_stdio(false);
	cin >> N >> D;
	for(int i=0; i<2*N; i++) {
		cin >> A[i] >> B[i];
		A[i] = -A[i], B[i] = -B[i];
		dist[i] = -1;
	}
	for(int i=0; i<N; i++) {
		if(B[i]==0)
			que[len++] = i, dist[i] = 1;
		else
			sA.insert(i);
		if(A[N+i]==0)
			que[len++] = N+i, dist[N+i] = 1;
		else
			sB.insert(N+i);
	}
	multiset<int,cmpA>::iterator itA;
	multiset<int,cmpB>::iterator itB;
	while(cur < len) {
		int i = que[cur];
		if(i < N) {
			while(1) {
				itB = sB.lower_bound(i);
				if(itB == sB.end() || A[*itB] > A[i]+D)
					break;
				dist[*itB] = dist[i] + 1;
				que[len++] = *itB;
				sB.erase(itB);
			}
		} else {
			while(1) {
				itA = sA.lower_bound(i);
				if(itA == sA.end() || B[*itA] > B[i]+D)
					break;
				dist[*itA] = dist[i] + 1;
				que[len++] = *itA;
				sA.erase(itA);
			}
		}
		cur++;
	}
	for(int i=0; i<N; i++)
		cout << dist[i] << '\n';
}