Submission #1675788


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define run(v) for(int k=head[v];k;k=e[k].ne)
#define v e[k].t
#define clr(a) memset(a,0,sizeof(a));
#define il inline
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back 
#define w1 first
#define w2 second
#define adm(a,b,c) {a=a+b;if(a>=c)a-=c;else if(a<0)a+=c;}
typedef pair<int,int> pa;
typedef long long ll;typedef long double ld;typedef unsigned long long ull;
const int N=1e6+5,M=5e7+5,INF=1e9,mod=1e9+7;
const ll linf=1e18;const double eps=1e-8,pi=acos(-1);
il int gmin(int &a,int b){if(a>b)a=b;}il ll gmin(ll &a,ll b){if(a>b)a=b;}il int gmax(int &a,int b){if(a<b)a=b;}il ll gmax(ll &a,ll b){if(a<b)a=b;}
il void read(ll&x){ll f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il ll read(ll&x,ll&y){read(x);read(y);}
il void read(int&x){int f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il int read(int&x,int&y){read(x);read(y);}
il void read(int&a,int&b,int&c){read(a);read(b);read(c);}il void read(ll&a,ll&b,ll&c){read(a);read(b);read(c);}
il int read(){int x;read(x);return x;}
il ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;}il ll qpow(ll a,ll b){ll ret=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod;return ret;}
il ll qmul(ll a,ll b,ll p){ll ret=0;for(;b;b>>=1,a=(a<<1)%p)if(b&1)adm(ret,a,p);return ret;}il ll qmul(ll a,ll b){ll ret=0;for(;b;b>>=1,a=(a<<1)%mod)if(b&1)adm(ret,a,mod);return ret;}
il void judge(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);}
il void gen(){freopen("data.in","w",stdout);}
int n,x[N],y[N],tot,rt;
pa p[N];int o;
struct edge{int t,ne;}e[N];
int head[N],ec,id[N];
#define YES(a) ((a)<<1)
#define NO(a) (((a)<<1)|1)
#define REV(a) ((a)^1)
#define mid ((l+r)>>1)
void adde(int a,int b){
	//printf("%d %d\n",a,b);
	e[++ec]=(edge){b,head[a]};head[a]=ec;
	a=REV(a);b=REV(b);swap(a,b);
	e[++ec]=(edge){b,head[a]};head[a]=ec;
}
int dfn[N],low[N],st[N],inst[N],bel[N],top,scc,dex;
void tarjan(int x){
	dfn[x]=low[x]=++dex;st[++top]=x;inst[x]=1;
	run(x)if(!dfn[v])tarjan(v),gmin(low[x],low[v]);else
		if(inst[v])gmin(low[x],dfn[v]);
	if(dfn[x]==low[x]){
		scc++;
		while(st[top]!=x)bel[st[top]]=scc,inst[st[top--]]=0;
		bel[x]=scc;inst[x]=0;top--;
	}
}
int ls[N],rs[N];
void gao(int k,int l,int r,int x,int y,int id){
	if(l==x&&r==y){if(l!=r)adde(id,YES(k));else adde(id,k);return;}
	if(y<=mid)gao(ls[k],l,mid,x,y,id);else
	if(x> mid)gao(rs[k],mid+1,r,x,y,id);else{
		gao(ls[k],l,mid,x,mid,id);
		gao(rs[k],mid+1,r,mid+1,y,id);
	}
}
void build(int&k,int fa,int l,int r){
	if(l==r){
		k=REV(p[l].w2);
		if(fa)adde(YES(fa),k);
		return;
	}
	k=++tot;
	if(fa)adde(YES(fa),YES(k));
	build(ls[k],k,l,mid);
	build(rs[k],k,mid+1,r);
}
bool ok(int d){
	rep(i,1,tot*2)head[i]=dfn[i]=low[i]=bel[i]=inst[i]=ls[i]=rs[i]=0;
	tot=n;ec=scc=top=dex=0;
	build(rt,0,1,n+n);
	int l=1,r=1;
	rep(i,1,n+n){
		while(p[i].w1-p[l].w1>=d)l++;
		while(r<n+n&&p[r+1].w1-p[i].w1<d)r++;
		if(l<i)gao(rt,1,n+n,l,i-1,p[i].w2);
		if(r>i)gao(rt,1,n+n,i+1,r,p[i].w2);
	}
	rep(i,2,tot*2+1)
		if(!dfn[i])tarjan(i);
	rep(i,1,n)if(bel[YES(i)]==bel[NO(i)])return 0;
	return 1;
}
int main(){
	read(n);rep(i,1,n)read(x[i],y[i]),p[++o]=pa(x[i],YES(i)),p[++o]=pa(y[i],NO(i));//no yes
	sort(p+1,p+1+o);
	int r=1e9,l=1,res=0;
	while(l<=r){
		if(ok(mid))
			res=mid,l=mid+1;
				else r=mid-1;
	}
	cout<<res<<endl;
}

Submission Info

Submission Time
Task F - Flags
User xjt
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3772 Byte
Status RE
Exec Time 413 ms
Memory 32512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1200
Status
AC × 3
AC × 25
RE × 5
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 8 ms 22784 KB
00_example_02.txt AC 8 ms 22784 KB
00_example_03.txt AC 8 ms 22784 KB
01.txt AC 14 ms 22784 KB
02.txt AC 10 ms 22784 KB
03.txt AC 8 ms 22784 KB
04.txt AC 8 ms 22784 KB
05.txt AC 8 ms 22784 KB
06.txt AC 413 ms 32512 KB
07.txt AC 405 ms 32512 KB
08.txt AC 319 ms 32512 KB
09.txt AC 13 ms 22784 KB
10.txt AC 10 ms 22784 KB
11.txt AC 8 ms 22784 KB
12.txt AC 9 ms 22784 KB
13.txt AC 9 ms 22784 KB
14.txt AC 279 ms 32384 KB
15.txt AC 298 ms 32384 KB
16.txt AC 279 ms 32384 KB
17.txt AC 14 ms 22784 KB
18.txt AC 10 ms 22784 KB
19.txt AC 356 ms 32512 KB
20.txt AC 354 ms 32512 KB
21.txt RE 199 ms 32384 KB
22.txt RE 147 ms 32384 KB
23.txt RE 150 ms 32384 KB
24.txt RE 138 ms 32256 KB
25.txt RE 133 ms 32256 KB
26.txt AC 409 ms 32512 KB
27.txt AC 8 ms 22784 KB