Submission #1676033
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
inline void judge(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
namespace SAT{
const int maxn=300005,maxm=1e6;
int tot,head[maxn],t[maxm],ne[maxm],num,n,dfn[maxn],low[maxn],S[maxn],top,clk,bl[maxn];
bool vis[maxn],ins[maxn];
inline void addedge(int x,int y){
ne[++num]=head[x];head[x]=num;t[num]=y;
// printf("%d %d\n",x,y);
}
inline void init(int _n){
rep(i,2,2*_n+1)head[i]=-1;clk=0;tot=0;top=0;
memset(vis,0,sizeof(vis));memset(ins,0,sizeof(ins));
num=0;n=_n;
}
inline void tarjan(int x){
low[x]=dfn[x]=++clk;vis[x]=1;S[++top]=x;ins[x]=1;
forE(i,x)if(!vis[t[i]]){
tarjan(t[i]);low[x]=min(low[x],low[t[i]]);
}else if(ins[t[i]])
low[x]=min(low[x],dfn[t[i]]);
if(low[x]==dfn[x]){
tot++;
while(S[top]!=x){
bl[S[top]]=tot;
ins[S[top]]=0;
top--;
}
bl[x]=tot;ins[x]=0;top--;
}
}
inline bool check(){
rep(i,2,2*n+1)if(!vis[i])tarjan(i);
rep(i,1,n)if(bl[2*i]==bl[2*i+1])return 0;
return 1;
}
}
inline void addedge(int x,int y,int vx,int vy){
// printf("%d %d %d %d\n",x,y,vx,vy);
SAT::addedge(2*x+vx,2*y+vy);
SAT::addedge(2*y+((vy)^1),2*x+(vx^1));
}
namespace seg{
const int maxn=8e4;
int id[maxn],tot,l[maxn],r[maxn];
inline void build(int x,int lq,int rq){
l[x]=lq;r[x]=rq;
if(lq==rq){
id[x]=lq;
return;
}id[x]=++tot;int md=(lq+rq)>>1;
build(ls(x),lq,md);build(rs(x),md+1,rq);
}
inline void add(int x){
if(l[x]==r[x])return;
add(ls(x));add(rs(x));
addedge(id[x],id[ls(x)],0,0);
addedge(id[x],id[rs(x)],0,0);
}
inline void add(int x,int lq,int rq,int nd){
if(lq>rq)return;
if(lq<=l[x]&&r[x]<=rq){
addedge(nd,id[x],1,0);
return;
}int md=(l[x]+r[x])>>1;
if(lq<=md)add(ls(x),lq,rq,nd);
if(rq> md)add(rs(x),lq,rq,nd);
}
}
const int maxn=2e4;
int x[maxn],y[maxn];
int rkx[maxn],rky[maxn];
map<int,int> zb;
pin h[maxn<<1];
int n,tot,tr[maxn];
inline bool check(int v){
// puts("===============================");
// printf("!%d\n",v);
SAT::init(seg::tot);
// SAT::init(2*n);
seg::add(1);
rep(i,1,n)
addedge(rkx[i],rky[i],1,0),addedge(rkx[i],rky[i],0,1);
int j=1;
rep(i,1,2*n){
while(j<2*n&&tr[i]-tr[j]>=v)j++;
// if(v==3)fprintf(stderr, "%d %d\n", i,j);
seg::add(1,j,i-1,i);
// rep(k,j,i-1)addedge(i,k,1,0);
} j=2*n;
per(i,2*n,1){
while(j>1&&tr[j]-tr[i]>=v)j--;
seg::add(1,i+1,j,i);
// rep(k,i+1,j)addedge(i,k,1,0);
}
return SAT::check();
}
int main(){
read(n);
rep(i,1,n)read(x[i]),read(y[i]);
rep(i,1,n)h[++tot]=mk(x[i],2*i),h[++tot]=mk(y[i],2*i+1);
sort(h+1,h+1+tot);int now=0;
rep(i,1,tot){
if(h[i].w2&1)
rky[h[i].w2/2]=i;
else
rkx[h[i].w2/2]=i;
}
rep(i,1,tot){
tr[i]=h[i].w1;
}
seg::tot=2*n;seg::build(1,1,2*n);
int l=0,r=1e9,ans=0;
while(l<=r){
int md=(l+r)>>1;
if(check(md)){
ans=md;
l=md+1;
}else{
r=md-1;
}
}
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
Scape |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3794 Byte |
Status |
RE |
Exec Time |
381 ms |
Memory |
16256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
8832 KB |
00_example_02.txt |
AC |
5 ms |
8832 KB |
00_example_03.txt |
AC |
5 ms |
8832 KB |
01.txt |
AC |
12 ms |
8960 KB |
02.txt |
AC |
7 ms |
8960 KB |
03.txt |
AC |
5 ms |
8832 KB |
04.txt |
AC |
6 ms |
8832 KB |
05.txt |
AC |
6 ms |
8832 KB |
06.txt |
AC |
309 ms |
15744 KB |
07.txt |
AC |
305 ms |
15872 KB |
08.txt |
AC |
330 ms |
15872 KB |
09.txt |
AC |
12 ms |
8960 KB |
10.txt |
AC |
7 ms |
8832 KB |
11.txt |
AC |
5 ms |
8832 KB |
12.txt |
AC |
6 ms |
8832 KB |
13.txt |
AC |
6 ms |
8832 KB |
14.txt |
AC |
302 ms |
16128 KB |
15.txt |
AC |
301 ms |
16256 KB |
16.txt |
AC |
299 ms |
16128 KB |
17.txt |
AC |
14 ms |
8960 KB |
18.txt |
AC |
8 ms |
8832 KB |
19.txt |
AC |
368 ms |
15872 KB |
20.txt |
AC |
335 ms |
15872 KB |
21.txt |
RE |
117 ms |
15104 KB |
22.txt |
RE |
119 ms |
15104 KB |
23.txt |
RE |
117 ms |
15104 KB |
24.txt |
RE |
115 ms |
15104 KB |
25.txt |
RE |
115 ms |
15104 KB |
26.txt |
AC |
381 ms |
16128 KB |
27.txt |
AC |
5 ms |
8832 KB |