Submission #1119850

---

Source Code Expand

#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=10000;
const int MAXZ=2*MAXN+2*MAXN;
const int MAXLG2N=15;
const int MAXM=4*MAXN+8*MAXN+8*MAXN*MAXLG2N;
typedef struct P { int x,id; } P;
bool operator<(const P &a,const P &b) { if(a.x!=b.x) return a.x<b.x; return a.id<b.id; }

int n;
int a[MAXN],b[MAXN];
P p[2*MAXN]; int pos[2*MAXN];

int key[2*MAXZ],minkey[2*MAXZ],nkey;
int stck[2*MAXZ],nstck;
bool onstck[2*MAXZ];
int comp[2*MAXZ],ncomp;

int nz;
int sz[8*MAXN];
int ghead[2*MAXZ],gto[MAXM],gnxt[MAXM],m;

void tarjan(int at,int D=0) {
	key[at]=minkey[at]=nkey++; stck[nstck++]=at,onstck[at]=true;
	for(int x=ghead[at];x!=-1;x=gnxt[x]) {
		int to=gto[x];
		//REP(dd,D) printf("  "); printf("%c%d->%c%d\n",at%2==0?'a':'b',at/2,to%2==0?'a':'b',to/2);
		if(key[to]==-1) {
			tarjan(to,D+1);
			minkey[at]=min(minkey[at],minkey[to]);
		} else if(onstck[to]) {
			minkey[at]=min(minkey[at],key[to]);
		}
	}
	if(minkey[at]==key[at]) {
		while(onstck[at]) { int to=stck[--nstck]; comp[to]=ncomp; onstck[to]=false; } ++ncomp;
	}
}

void addedge(int a,int b) { gnxt[m]=ghead[a]; ghead[a]=m; gto[m]=b; ++m; }
void sinit(int x,int l,int r) {
	if(l==r) { sz[x]=l; return; }
	int m=l+(r-l)/2;
	sinit(2*x+1,l,m); sinit(2*x+2,m+1,r);
	sz[x]=nz++; //printf("x=%d %d..%d=%d\n",x,l,r,sz[x]);
	addedge(2*sz[x]+1,2*sz[2*x+1]+1); addedge(2*sz[2*x+1]+0,2*sz[x]+0);
	addedge(2*sz[x]+1,2*sz[2*x+2]+1); addedge(2*sz[2*x+2]+0,2*sz[x]+0);
}
void sappend(int x,int l,int r,int L,int R,int I) {
	if(L<=l&&r<=R) { addedge(2*I+0,2*sz[x]+1); return; }
	int m=l+(r-l)/2;
	if(L<=m) sappend(2*x+1,l,m,L,R,I);
	if(m+1<=R) sappend(2*x+2,m+1,r,L,R,I);
}


bool ok(int d) {
	m=0; nz=2*n; memset(ghead,-1,sizeof(ghead));
	REP(i,2*n) addedge(2*i+0,2*pos[p[i].id^1]+1);
	REP(i,2*n) addedge(2*i+1,2*pos[p[i].id^1]+0);
	sinit(0,0,2*n-1); //int mx=0,mm=m;
	REP(i,2*n) {
		int l; { int L=-1,R=i; while(L+1<R) { int M=L+(R-L)/2; if(p[i].x-p[M].x<d) R=M; else L=M; } l=R; }
		int r; { int L=i,R=2*n; while(L+1<R) { int M=L+(R-L)/2; if(p[M].x-p[i].x<d) L=M; else R=M; } r=L; }
		if(l<=i-1) sappend(0,0,2*n-1,l,i-1,i);
		if(i+1<=r) sappend(0,0,2*n-1,i+1,r,i);
	}
	//printf("nz=%d m=%d (%d) mx=%d\n",nz,m,mm,mx);
	//REP(i,2*nz) { printf("%c%d:",i%2==0?'T':'F',i/2); REPSZ(j,e[i]) printf(" %c%d",e[i][j]%2==0?'T':'F',e[i][j]/2); puts(""); }
	nkey=0; nstck=0; ncomp=0; REP(i,2*nz) onstck[i]=false,key[i]=comp[i]=-1;
	REP(i,2*nz) if(key[i]==-1) tarjan(i);
	REP(i,nz) if(comp[2*i+0]==comp[2*i+1]) return false;
	return true;
}



int solve() {
	REP(i,n) p[2*i+0].x=a[i],p[2*i+0].id=2*i+0,p[2*i+1].x=b[i],p[2*i+1].id=2*i+1;  sort(p,p+2*n); REP(i,2*n) pos[p[i].id]=i;
	//REP(i,2*n) printf("%c%d ",p[i].id%2==0?'a':'b',p[i].id/2); puts("");
	//REP(i,2*n) printf("%d ",pos[i]); puts("");
	//printf("ok(4)=%d\n",ok(4)?1:0); exit(0);
	int l=0,h=1000000000;
	while(l+1<h) {
		int m=l+(h-l)/2;
		//printf("testing %d\n",m);
		if(ok(m)) l=m; else h=m;
	}
	return l;
}


void run() {
	scanf("%d",&n); REP(i,n) scanf("%d%d",&a[i],&b[i]);
	printf("%d\n",solve());
}

int myrand() { return (rand()%10000)*10000+rand()%10000; }
void test() {
	n=MAXN; REP(i,n) a[i]=myrand(),b[i]=myrand();
	printf("%d\n",solve());
}

int main() {
	run();
	//test();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void run()’:
./Main.cpp:124:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); REP(i,n) scanf("%d%d",&a[i],&b[i]);
                ^
./Main.cpp:124:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); REP(i,n) scanf("%d%d",&a[i],&b[i]);
                                                    ^

Judge Result