Submission #1630483

---

Source Code Expand

#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > 
#define pii pair<int,int> 
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define SZ(x) ((int)x.size())
using namespace std;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
const int BufferSize=1<<16;
char buffer[BufferSize],*Bufferhead,*Buffertail;
bool Terminal;
inline char Getchar(){
	if(Bufferhead==Buffertail){
		int l=fread(buffer,1,BufferSize,stdin);
		if(!l){Terminal=1;return 0;}
		Buffertail=(Bufferhead=buffer)+l;
	}
	return *Bufferhead++;
}
template<class T>inline bool read(T &x){
	x=0;char c=Getchar(),rev=0;
	while(c<'0'||c>'9'){c=Getchar();rev|=c=='-';if(Terminal)return 0;}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
	if(c=='.'){
		c=Getchar();double t=0.1;
		while(c>='0'&&c<='9') x=x+(c-'0')*t,c=Getchar(),t=t/10;
	}
	x=rev?-x:x;
	return 1;
}
template<class T1,class T2> inline bool read(T1 &x,T2 &y){return read(x)&read(y);}
template<class T1,class T2,class T3> inline bool read(T1 &x,T2 &y,T3 &z){return read(x)&read(y)&read(z);}
template<class T1,class T2,class T3,class T4> inline bool read(T1 &x,T2 &y,T3 &z,T4 &w){return read(x)&read(y)&read(z)&read(w);}
inline bool reads(char *x){
	char c=Getchar();
	while(c<33||c>126){c=Getchar();if(Terminal)return 0;}
	while(c>=33&&c<=126) (*x++)=c,c=Getchar();
	*x=0;return 1;
}
template<class T>inline void print(T x,const char c='\n'){
	if(!x){putchar('0');putchar(c);return;}
	if(x<0) putchar('-'),x=-x;
	int m=0,a[20];
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');
	putchar(c);
}
//--------------------------------head---------------------------------------------

const int N=140005,M=5000005,mod=1e9+7;
template<class T,class S> inline void ch(T &x,const S y){x=(x+y)%mod;}
inline int exp(int x,int y,const int mod=::mod){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

struct node{int to,next;}p[M];
int n,m,inf,cnt,tot,xx[N],yy[N],num[N][2],pp[N];
pii a[N];
int vis[N],g[N],f[N];
vi seq;

inline int pos(int x,int y=0){return lower_bound(a+1,a+n*2+1,mp(x,y))-a;}
void add(int x,int y){
	p[++tot]=(node){y,g[x]};g[x]=tot;
	p[++tot]=(node){x,f[y]};f[y]=tot;
}
inline void build(int l,int r,int k){
	if(l==r){pp[l]=k;gmax(cnt,k);return;}
	int mid=l+r>>1;
	build(l,mid,ls);build(mid+1,r,rs);
	add(num[k][0],num[ls][0]);add(num[ls][1],num[k][1]);
	add(num[k][0],num[rs][0]);add(num[rs][1],num[k][1]);
}
inline void get(int l,int r,int x,int y,int k,int p){
	if(x>y) return;
	if(x<=l&&r<=y){
		add(num[pp[p]][1],num[k][0]);
		add(num[k][1],num[pp[p]][0]);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) get(l,mid,x,y,ls,p);
	if(y>mid) get(mid+1,r,x,y,rs,p);
}
inline void pre(int x){
	vis[x]=1;
	for(int i=f[x];i;i=p[i].next){
		int y=p[i].to;
		if(!vis[y]) pre(y);
	}
	seq.pb(x);
}
inline void dfs(int x,int t){
	vis[x]=t;
	for(int i=g[x];i;i=p[i].next){
		int y=p[i].to;
		if(!vis[y]) dfs(y,t);
	}
}
inline bool check(){
	clr(vis,0);seq.clear();
	for(int i=1;i<=m;i++)
		if(!vis[i]) pre(i);
	clr(vis,0);
	for(int i=m,j=0;i;i--)
		if(!vis[seq[i-1]]) dfs(seq[i-1],++j);
	for(int i=1;i<=cnt;i++)
		if(vis[num[i][0]]==vis[num[i][1]]) return 0;
	return 1;
}
inline bool check(int D){
	tot=0;
	for(int i=1;i<=m;i++) g[i]=f[i]=0;
	build(1,n*2,1);
	for(int i=1;i<=n;i++){
		int x=pos(xx[i],i),y=pos(yy[i],i);
		add(num[pp[y]][0],num[pp[x]][1]);add(num[pp[x]][0],num[pp[y]][1]);
		get(1,n*2,pos(xx[i]-D+1),x-1,1,x);
		get(1,n*2,x+1,pos(xx[i]+D)-1,1,x);
		get(1,n*2,pos(yy[i]-D+1),y-1,1,y);
		get(1,n*2,y+1,pos(yy[i]+D)-1,1,y);
	}
	return check();
}

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&xx[i],&yy[i]);
		a[i]=mp(xx[i],i);
		a[i+n]=mp(yy[i],i);
		gmax(inf,xx[i]);gmax(inf,yy[i]);
	}
	sort(a+1,a+n*2+1);
	build(1,n*2,1);m=cnt*2;
	for(int i=1;i<=cnt;i++)
		num[i][0]=i*2,num[i][1]=i*2-1;
	int l=0,r=inf;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid; else r=mid-1;	
	}
	print(r);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:152:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:154:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&xx[i],&yy[i]);
                              ^

Judge Result