C++14(g++5.4) 解法, 执行用时: 27ms, 内存消耗: 1664K, 提交时间: 2020-10-20 11:07:49

#include <stdio.h>
#include <algorithm>
using namespace std;
struct node
{
	int pos,id;
	bool operator<(const node &a)const
	{
		return pos<a.pos;
	}
}a[500010],q[500010];
int b[500010],c[500010];
int vis[500010];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].pos,&a[i].id);
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)b[i]=a[i].pos,c[i]=a[i].id;
	sort(c+1,c+1+n);
	int len2=unique(c+1,c+1+n)-c-1;
	int l=1,r=0,ans=1e9;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int id=lower_bound(c+1,c+1+len2,a[i].id)-c;
		vis[id]++;
		q[++r].pos=a[i].pos;q[r].id=id;
		if(vis[id]==1)cnt++;
		while(l<=r&&vis[q[l].id]>1)vis[q[l].id]--,l++;
		if(cnt==len2)ans=min(ans,a[i].pos-q[l].pos);
	}
	printf("%d\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 30ms, 内存消耗: 2052K, 提交时间: 2020-10-19 20:46:11

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e4+5,inf=2e9;
struct node{int x,y;}a[N];
int n,b[N],len,ans=inf,cnt[N];
bool cmp(node a,node b){return a.x<b.x;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y),b[++len]=a[i].y;
	sort(b+1,b+len+1);len=unique(b+1,b+len+1)-b-1;
	for(int i=1;i<=n;i++)a[i].y=lower_bound(b+1,b+len+1,a[i].y)-b;
	sort(a+1,a+n+1,cmp);
	for(int i=1,l=1,now=0;i<=n;i++){
		cnt[a[i].y]++;if(cnt[a[i].y]==1)now++;
		while(now==len&&cnt[a[l].y]>1)cnt[a[l].y]--,l++;
		if(now==len)ans=min(ans,a[i].x-a[l].x);
	}
	printf("%d\n",ans);
	return 0;
}