Submission #1676112

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int n,p[100010],q[100010];
pair<int,int> dt[200010];
vector <int> des[1000100];
int po;
int dfn[1000100],low[1000100],st[1000100],bel[1000100],tim,js,top;
bool ins[1000100];
void tarjan(int s)
{
    dfn[s]=low[s]=++tim;
    st[++top]=s;ins[s]=true;
    for (int k=0;k<des[s].size();k++)
    {
        if (!dfn[des[s][k]]) {tarjan(des[s][k]);low[s]=min(low[s],low[des[s][k]]);}
        else if (ins[des[s][k]]) low[s]=min(low[s],dfn[des[s][k]]);
    }
    if (dfn[s]==low[s])
    {
        js++;
        while (st[top]!=s)
        {
            bel[st[top]]=js;
            ins[st[top]]=false;top--;
        }
        bel[st[top]]=js;
        ins[st[top]]=false;top--;
    }
}
void build(int root,int l,int r)
{
	po=max(po,root+2*n);
	if (l==r)
	{
		des[root+2*n].push_back((dt[l].second<0)?-dt[l].second+n:dt[l].second);
		return;
	}
	int mid=(l+r)>>1;
	des[root+2*n].push_back(root*2+2*n);
	des[root+2*n].push_back(root*2+1+2*n);
	build(root*2,l,mid);build(root*2+1,mid+1,r);
}
void find(int ql,int qr,int s,int root=1,int pl=1,int pr=2*n)
{
	if ((pl==ql)&&(pr==qr))
	{
		des[s].push_back(root+2*n);
		return;
	}
	int mid=(pl+pr)>>1;
	if (qr<=mid) find(ql,qr,s,root*2,pl,mid);
	else if (ql>mid) find(ql,qr,s,root*2+1,mid+1,pr);
	else
	{
		find(ql,mid,s,root*2,pl,mid);
		find(mid+1,qr,s,root*2+1,mid+1,pr);
	}
	/*for (int i=ql;i<=qr;i++)
	{
		cerr<<s<<' '<<((dt[i].second<0)?-dt[i].second+n:dt[i].second)<<endl;
		des[s].push_back((dt[i].second<0)?-dt[i].second+n:dt[i].second);
	}*/
}
bool check(int lim)
{
	for (int i=1;i<=po;i++) {des[i].clear();dfn[i]=low[i]=bel[i]=0;}tim=js=top=0;
	po=2*n;
	build(1,1,2*n);
	int d=0;
	for (int i=1;i<=2*n;i++)
	{
		while ((d+1<i)&&(dt[i].first-dt[d+1].first>=lim)) d++;
		if (d+1<=i-1) find(d+1,i-1,(dt[i].second<0)?-dt[i].second:dt[i].second+n);
	}
	d=2*n+1;
	for (int i=2*n;i>=1;i--)
	{
		while ((d-1>i)&&(dt[d-1].first-dt[i].first>=lim)) d--;
		if (i+1<=d-1) find(i+1,d-1,(dt[i].second<0)?-dt[i].second:dt[i].second+n);
	}
	for (int i=1;i<=po;i++) if (!dfn[i]) tarjan(i);
	for (int i=1;i<=n;i++) if (bel[i]==bel[i+n]) return false;
	return true;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		dt[i]=make_pair(x,-i);
		dt[i+n]=make_pair(y,i);
	}
	sort(dt+1,dt+2*n+1);
	for (int i=1;i<=2*n;i++)
	{
		if (dt[i].second<0) p[-dt[i].second]=i;
		else q[dt[i].second]=i;
	}
	int l=0,r=1e9+10;
	//cerr<<check(3)<<endl;return 0;
	while (l+1!=r)
	{
		int mid=(l+r)>>1;
		if (check(mid)) l=mid;else r=mid;
	}
	printf("%d\n",l);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:90:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int x,y;scanf("%d%d",&x,&y);
                              ^

Judge Result