Submission #1630474


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=100005,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;
}

int n,m,inf,cnt,xx[N],yy[N],num[N][2],pp[N];
pii a[N];
int vis[N];
vi g[N],f[N],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){g[x].pb(y);f[y].pb(x);}
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 y:f[x])
		if(!vis[y]) pre(y);
	seq.pb(x);
}
inline void dfs(int x,int t){
	vis[x]=t;
	for(int y:g[x])
		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){
	for(int i=1;i<=m;i++) g[i].clear(),f[i].clear();
	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

Submission Time
Task F - Flags
User rqgao2014
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 4652 Byte
Status AC
Exec Time 2534 ms
Memory 40180 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:143:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:145: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

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 3
AC × 30
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 5 ms 10496 KB
00_example_02.txt AC 5 ms 10496 KB
00_example_03.txt AC 6 ms 10496 KB
01.txt AC 26 ms 11264 KB
02.txt AC 13 ms 10752 KB
03.txt AC 8 ms 10496 KB
04.txt AC 8 ms 10496 KB
05.txt AC 9 ms 10624 KB
06.txt AC 1473 ms 33396 KB
07.txt AC 1528 ms 33428 KB
08.txt AC 1435 ms 33524 KB
09.txt AC 26 ms 11136 KB
10.txt AC 13 ms 10752 KB
11.txt AC 8 ms 10496 KB
12.txt AC 8 ms 10496 KB
13.txt AC 9 ms 10496 KB
14.txt AC 1305 ms 29300 KB
15.txt AC 1317 ms 29172 KB
16.txt AC 1534 ms 29172 KB
17.txt AC 28 ms 11136 KB
18.txt AC 14 ms 10752 KB
19.txt AC 1683 ms 32628 KB
20.txt AC 2084 ms 32500 KB
21.txt AC 2534 ms 35700 KB
22.txt AC 2237 ms 33908 KB
23.txt AC 2429 ms 40180 KB
24.txt AC 2080 ms 38260 KB
25.txt AC 1684 ms 38004 KB
26.txt AC 1939 ms 35572 KB
27.txt AC 7 ms 10496 KB