luogu2698 [USACO12MAR]花盆Flowerpot

单调队列+二分答案

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

struct Node{

	int x, y;

}nd[100005];

int n, d, ans, q1[100005], q2[100005], l1, r1, l2, r2;

bool cmp(Node u, Node v){

	return u.x<v.x;

}

bool check(int lim){

	l1 = 1, r1 = 0;

	l2 = 1, r2 = 0;

	for(int i=1; i<=n; i++){

		while(l1<=r1 && nd[q1[l1]].x<nd[i].x-lim)	l1++;

		while(l1<=r1 && nd[q1[r1]].y>nd[i].y)	r1--;

		q1[++r1] = i;

		while(l2<=r2 && nd[q2[l2]].x<nd[i].x-lim)	l2++;

		while(l2<=r2 && nd[q2[r2]].y<nd[i].y)	r2--;

		q2[++r2] = i;

		if(nd[q2[l2]].y-nd[q1[l1]].y>=d)	return true;

	}

	return false;

}

int main(){

	cin>>n>>d;

	for(int i=1; i<=n; i++)

		scanf("%d %d", &nd[i].x, &nd[i].y);

	sort(nd+1, nd+1+n, cmp);

	int l=0, r=nd[n].x-nd[1].x, mid;

	while(l<=r){

		mid = (l + r) >> 1;

		if(check(mid)){

			ans = mid;

			r = mid - 1;

		}

		else	l = mid + 1;

	}

	if(ans==0)	cout<<"-1"<<endl;

	else	cout<<ans<<endl;

	return 0;

}