Submission #1671229
Source Code Expand
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=2e5;
int gi() {
int w=0;bool q=1;char c=getchar();
while ((c<'0'||c>'9') && c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
return q? w:-w;
}
pair<int,int>p[N];
int s[N],nd[N],id[N],node;
int head[N],nxt[N],to[N],tot;
int dfn[N],low[N],st[N],rt[N],top,cnt,scc;bool in[N];
inline void link(int a,int b) { to[++tot]=b,nxt[tot]=head[a],head[a]=tot; }
inline void dfs(int k) {
dfn[k]=low[k]=++cnt;
in[st[++top]=k]=true;
for (int i=head[k];i;i=nxt[i])
if (!dfn[to[i]])
dfs(to[i]),low[k]=min(low[k],low[to[i]]);
else if (in[to[i]]) low[k]=min(low[k],dfn[to[i]]);
if (low[k]==dfn[k]) {
rt[k]=++scc;in[k]=false;
while (st[top]!=k) rt[st[top]]=scc,in[st[top--]]=false;
top--;
}
}
#define lc (i<<1)
#define rc (lc|1)
inline void build(int i,int l,int r) {
nd[i]=++node;
if (l==r) id[s[p[l].second]^l]=node;
else {
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
}
inline void init(int i,int l,int r) {
if (l==r) return;
int mid=(l+r)>>1;
link(nd[i],nd[lc]);
link(nd[i],nd[rc]);
init(lc,l,mid);
init(rc,mid+1,r);
}
inline void add(int i,int l,int r,int L,int R,int k) {
if (L<=l&&r<=R) link(k,nd[i]);
else {
int mid=(l+r)>>1;
if (L<=mid) add(lc,l,mid,L,R,k);
if (mid<R) add(rc,mid+1,r,L,R,k);
}
}
int main()
{
int n=gi(),i,m=0,l,r,mid,L,R;
for (i=1;i<=n;i++)
p[++m]=make_pair(gi(),i),p[++m]=make_pair(gi(),i);
sort(p+1,p+1+m);
for (i=1;i<=m;i++) s[p[i].second]^=i;
l=0,r=p[m].first-p[1].first;
build(1,1,m);
while (l!=r) {
mid=(l+r+1)>>1;
tot=cnt=scc=0;
for (i=1;i<=node;i++) head[i]=dfn[i]=0;
init(1,1,m);
for (i=1,L=R=1;i<=m;i++) {
while (p[i].first-p[L].first>=mid) L++;
if (L<i) add(1,1,m,L,i-1,id[i]);
while (R<m&&p[R+1].first-p[i].first<mid) R++;
if (i<R) add(1,1,m,i+1,R,id[i]);
}
for (i=1;i<=node;i++) if (!dfn[i]) dfs(i);
for (i=1;i<=m;i++) if (rt[id[i]]==rt[id[s[p[i].second]^i]]) break;
if (i<=m) r=mid-1;
else l=mid;
}
cout<<l<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
laofu |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2401 Byte |
Status |
TLE |
Exec Time |
5255 ms |
Memory |
6528 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 |
3 ms |
6400 KB |
00_example_02.txt |
AC |
2 ms |
4352 KB |
00_example_03.txt |
AC |
3 ms |
6400 KB |
01.txt |
AC |
8 ms |
6400 KB |
02.txt |
AC |
5 ms |
6400 KB |
03.txt |
AC |
3 ms |
6400 KB |
04.txt |
AC |
4 ms |
6400 KB |
05.txt |
AC |
4 ms |
6400 KB |
06.txt |
TLE |
5255 ms |
6528 KB |
07.txt |
TLE |
5255 ms |
6528 KB |
08.txt |
TLE |
5255 ms |
6400 KB |
09.txt |
AC |
8 ms |
6400 KB |
10.txt |
AC |
5 ms |
6400 KB |
11.txt |
AC |
3 ms |
6400 KB |
12.txt |
AC |
3 ms |
6400 KB |
13.txt |
AC |
3 ms |
6400 KB |
14.txt |
TLE |
5255 ms |
6528 KB |
15.txt |
TLE |
5255 ms |
6400 KB |
16.txt |
TLE |
5255 ms |
6528 KB |
17.txt |
AC |
9 ms |
6400 KB |
18.txt |
AC |
5 ms |
6400 KB |
19.txt |
TLE |
5255 ms |
6528 KB |
20.txt |
TLE |
5255 ms |
6528 KB |
21.txt |
TLE |
5255 ms |
6400 KB |
22.txt |
TLE |
5255 ms |
6400 KB |
23.txt |
TLE |
5255 ms |
6400 KB |
24.txt |
TLE |
5255 ms |
6400 KB |
25.txt |
TLE |
5255 ms |
6400 KB |
26.txt |
TLE |
5255 ms |
6528 KB |
27.txt |
AC |
3 ms |
6400 KB |