Submission #8526354

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<cstring>
#define P pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define N 200010
using namespace std;
int nxt[N<<2],to[N<<2],head[N],cnt;
void add(int u,int v)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}
int dfn[N],low[N],id[N],ids,totn;
stack<int>s;
void tarjan(int u)
{
	dfn[u]=low[u]=++ids;
	s.push(u);
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(!dfn[v])
		{
			int v=to[i];
			tarjan(v);
			low[u]=min(low[v],low[u]);
		}
		else if(!id[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		int iu=0;
		totn++;
		do
		{
			id[iu=s.top()]=totn;
			s.pop();
		}while(iu!=u);
	}
}
P num[N];
int tree[N],tids;
void build(int u,int l,int r)
{
	if(l==r){tree[u]=num[l].se;return;}
	int mid=(l+r)>>1;
	tree[u]=++tids;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	add(tree[u],tree[u<<1]);
	add(tree[u],tree[u<<1|1]);
}
void insert(int u,int l,int r,int L,int R,int id)
{
	if(L>r || R<l) return;
	if(L<=l && r<=R)
	{
		add(id,tree[u]);
		return ;
	}
	int mid=(l+r)>>1;
	if(L<=mid) insert(u<<1,l,mid,L,R,id);
	if(R>mid) insert(u<<1|1,mid+1,r,L,R,id);
}
int n;
int lim[2][N];
void clear()
{
	memset(head,0,sizeof(head));
	cnt=ids=totn=0;tids=2*n;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(id,0,sizeof(id));
}
bool check(int x)
{
	clear();
	build(1,1,2*n);
	for(int i=1;i<=n;i++)
	{
		for(int o=0;o<=1;o++)
		{
			int l=lower_bound(num+1,num+2*n+1,MP(lim[o][i]-x+1,0))-num;
			int r=upper_bound(num+1,num+2*n+1,MP(lim[o][i]+x-1,2*n+1))-num-1;
			int u=lower_bound(num+1,num+2*n+1,MP(lim[o][i],(o^1)*n+i))-num;
			int ui=o*n+i;
            insert(1,1,2*n,l,u-1,ui);
            insert(1,1,2*n,u+1,r,ui);
		}
	}
	while(!s.empty()) s.pop();
	for(int i=1;i<=tids;i++)
	if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
	if(id[i]==id[i+n]) return false;
	return true;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&lim[0][i],&lim[1][i]);
	for(int i=1;i<=n;i++)
	{
		num[i*2-1]=MP(lim[0][i],i+n);
		num[i*2]=MP(lim[1][i],i);
	}
	sort(num+1,num+n*2+1);
	int l=0,r=1000000000;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	if(!check(l)) l--;
	printf("%d\n",l);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:107:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:108:59: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d%d",&lim[0][i],&lim[1][i]);
                                                           ^

Judge Result