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
2017-09-27 15:01:42+0900
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
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