Submission #1865575

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#define MAXN 100010
using namespace std;

struct edge{
	int to,next;
	edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[10000000];

int n,sizew,nump,numw;
int g[MAXN],nume;
pair<int,int> a[MAXN];
int dfn[MAXN],low[MAXN];
int last[MAXN];
int p[MAXN][2];
stack<int> S;
bool instack[MAXN];
int c[MAXN],numc;

void addEdge(int u,int v){
	e[nume]=edge(v,g[u]);
	g[u]=nume++;
}

void build(int x,int cl,int cr,int l,int r,int src){
	if(l<=cl && cr<=r){
		addEdge(p[sizew+src-1][1],p[x][0]);
		addEdge(p[x][1],p[sizew+src-1][0]);
		return;
	}
	int mid=(cl+cr)>>1;
	if(l<=mid) build(x<<1,cl,mid,l,r,src);
	if(r>mid) build(x<<1|1,mid+1,cr,l,r,src);
}

void tarjan(int x){
	S.push(x);
	instack[x]=1;
	dfn[x]=low[x]=++numw;
	for(int i=g[x];~i;i=e[i].next)
		if(!dfn[e[i].to]){
			tarjan(e[i].to);
			if(low[e[i].to]<low[x]) low[x]=low[e[i].to];
		}else if(instack[e[i].to]){
			if(dfn[e[i].to]<low[x]) low[x]=dfn[e[i].to];
		}
	if(dfn[x]==low[x]){
		++numc;
		while(S.top()!=x){
			instack[S.top()]=0;
			c[S.top()]=numc;
			S.pop();
		}
		instack[S.top()]=0;
		c[S.top()]=numc;
		S.pop();
	}
}

bool check(int lim){
	memset(g,-1,sizeof g);
	nump=nume=0;
	for(sizew=1;sizew<n;sizew<<=1);
	for(int i=1;i<=2*sizew-1;i++) p[i][0]=++nump;
	for(int i=1;i<=2*sizew-1;i++) p[i][1]=++nump;
	for(int i=sizew-1;i;i--){
		addEdge(p[i<<1][1],p[i][1]);
		addEdge(p[i<<1|1][1],p[i][1]);
		addEdge(p[i][0],p[i<<1][0]);
		addEdge(p[i][0],p[i<<1|1][0]);
	}
	memset(last,0,sizeof last);
	for(int i=1;i<=n;i++)
		if(last[a[i].second]){
			int j=last[a[i].second];
			addEdge(p[sizew+i-1][0],p[sizew+j-1][1]);
			addEdge(p[sizew+j-1][0],p[sizew+i-1][1]);
			addEdge(p[sizew+i-1][1],p[sizew+j-1][0]);
			addEdge(p[sizew+j-1][1],p[sizew+i-1][0]);
		}else last[a[i].second]=i;
	for(int i=n-1;i;i--)
		if(a[i+1].first-a[i].first<lim){
			int l=i+1,r=n;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(a[mid].first-a[i].first<lim) l=mid;
				else r=mid-1;
			}
			build(1,1,sizew,i+1,l,i);
		}
	memset(dfn,0,sizeof dfn);
	numc=numw=0;
	for(int i=1;i<=nump;i++)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
		if(c[p[sizew+i-1][0]]==c[p[sizew+i-1][1]]) return 0;
	return 1;
}

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		a[i*2-1]=make_pair(t1,i);
		a[i*2]=make_pair(t2,i);
	}
	n*=2;
	sort(a+1,a+n+1);
	int l=0,r=a[n].first-a[1].first;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	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:110:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
                        ^

Judge Result