Submission #1119778

---

Source Code Expand

#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#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 RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
     
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
struct edge {
    int next,to;
};
 
const int maxn=(int)(1e6)+5;
int fr[maxn];
int bi[maxn];
edge e[maxn];
int x[maxn],y[maxn];
int tb[maxn],n,tot,tote,idx;
map<int,int> hs;

inline void addedge(int u,int v) {
    ++tote;
    e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;
}

void build(int x,int l,int r,int fa) {
    bi[x]=++idx;
    if(fa) addedge(fa,bi[x]);
    if(l==r) {
        addedge(bi[x],l+tot);
        return;
    } 
    int mid=(l+r)>>1;
    build(x<<1,l,mid,bi[x]);
    build(x<<1|1,mid+1,r,bi[x]);
}
 
void add(int x,int l,int r,int s,int t,int v) {
    if(s<=l && r<=t) {
        addedge(v,bi[x]);return;
    }
    int mid=(l+r)>>1;
    if(s<=mid) add(x<<1,l,mid,s,t,v);
    if(mid<t) add(x<<1|1,mid+1,r,s,t,v);
}
 
int vis[maxn],ins[maxn];
int dfn[maxn],low[maxn];
int stk[maxn],id[maxn];
int cnt,dfs_cnt,top;
 
void dfs(int u) {  
    vis[u]=ins[u]=1;  
    dfn[u]=low[u]=++dfs_cnt;  
    stk[++top]=u;  
    RAL(i,u) {  
        int v=e[i].to;  
        if(!vis[v]) {  
            dfs(v);  
            low[u]=min(low[u],low[v]);  
        } else if(ins[v])   
            low[u]=min(low[u],dfn[v]);  
    }  
    if(dfn[u]==low[u]) {  
        cnt++;
        int v=-1;  
        while(u!=v) {  
            v=stk[top--];  
            ins[v]=0;  
            id[v]=cnt;
        } 
    } 
}
 
int vi[maxn];
inline int chk(int now) {
    memset(fr,-1,sizeof(fr));tote=0;
    idx=2*tot;build(1,1,tot,0);
    memset(vi,0,sizeof(vi));
    REP(i,1,n) {
        addedge(x[i]+tot,y[i]);
        addedge(y[i]+tot,x[i]);
        addedge(x[i],y[i]+tot);
        addedge(y[i],x[i]+tot);
    }
    int ps=1;
    REP(i,1,tot) {
        while(ps<=tot && tb[i]+now>tb[ps]) ps++;
        if(i+1<=ps-1) add(1,1,tot,i+1,ps-1,i);
    }
    ps=tot;
    PER(i,tot,1) {
        while(ps>=1 && tb[i]-now<tb[ps]) ps--;
        if(ps+1<=i-1) add(1,1,tot,ps+1,i-1,i);
    }
    memset(vis,0,sizeof(vis));cnt=dfs_cnt=0;
    REP(i,1,idx) if(!vis[i]) dfs(i);
    REP(i,1,tot) if(id[i]==id[i+tot]) return 0;
    return 1;
}
 
int main() {
    read(n);
    REP(i,1,n) {
        read(x[i]);read(y[i]);
        tb[++tot]=x[i];tb[++tot]=y[i];
    }
    sort(tb+1,tb+tot+1);
    PER(i,tot,1) hs[tb[i]]=i;
    REP(i,1,n) {
        x[i]=hs[x[i]]++;y[i]=hs[y[i]]++;
    } 
    int l=0,r=(int)(1e9);
    while(l<r) {
        int mid=(l+r)>>1;
        if(chk(mid+1)) l=mid+1;
        else r=mid;
    }  
    printf("%d\n",l);
    return 0;
}

Submission Info

Judge Result