Submission #1118369

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 100100;

pair<int, int> A[MAX];

vector<pair<int, int> > E;

vector<int> g[MAX];
vector<int> gr[MAX];

void add_edge(int x, int y)
{
	g[x].PB(y);
	gr[y].PB(x);
}

struct RHQ
{
	int n;
	int shift;
	int mx;

	void init(int tl, int tr, int v, vector<pair<int, int> > &E)
	{
		if (tl == tr)
		{
			mx = max(mx, v + shift + 1);
			add_edge(v + shift, E[tl].second);
			return;
		}

		int tm = (tl + tr) / 2;
		init(tl, tm, v*2, E);
		init(tm+1, tr, v*2+1, E);
		add_edge(v + shift, 2*v + shift);
		add_edge(v + shift, 2*v+1 + shift);
	}

	void init(vector<pair<int, int> >& E, int shift)
	{
		this->shift = shift;
		n = SZ(E);
		mx = 0;

		init(0, n-1, 1, E);
	}

	void add(int tl, int tr, int v, int l, int r, int x)
	{
	//	cout<<tl<<' '<<tr<<' '<<v<<' '<<l<<' '<<r<<' '<<x<<endl;
		if (tl == l && tr == r)
		{
			add_edge(x, v + shift);
			return;
		}
		if (l > r) return;

		int tm = (tl + tr) / 2;

		add(tl, tm, v*2, l, min(r, tm), x);
		add(tm+1, tr, v*2+1, max(l, tm + 1), r, x);
	}

	void add(int x, int L, int R)
	{
		add(0, n-1, 1, L, R, x);
	//	cout<<endl;
	}
} H;

int N;
int n;

bool U[MAX];
int C[MAX];
vector<int> ord;

void dfs1(int x)
{
	U[x] = true;
	FOR (i, 0, SZ(g[x]))
	{
		int to = g[x][i];
		if (U[to]) continue;
		dfs1(to);
	}

	ord.PB(x);
}

void dfs2(int x, int c)
{
	U[x] = true;
	C[x] = c;

	FOR (i, 0, SZ(gr[x]))
	{
		int to = gr[x][i];
		if (U[to]) continue;
		dfs2(to, c);
	}
}


bool can(int m)
{
	FOR (i, 0, N)
	{
		g[i].clear();
		gr[i].clear();
		U[i] = false;
	}

	ord.clear();

	H.init(E, 2*n);

	N = H.mx;

	/*FOR (i, 0, SZ(E))
	{
		cout<<E[i].first<<' '<<E[i].second<<endl;
	}
	cout<<endl;*/

	FOR (i, 0, SZ(E))
	{
		int p = E[i].first;
		int x = E[i].second;
		if (x < n) x += n;
		else x -= n;

		int pos = upper_bound(ALL(E), MP(p + m-1, INF)) - E.begin() - 1;

		H.add(x, i+1, pos);
		//cout<<i<<' '<<x<<' '<<pos<<' ';

		pos = upper_bound(ALL(E), MP(p - m , INF)) - E.begin();
		//cout<<pos<<endl;
		H.add(x, pos, i-1);
	}


	FOR (i, 0, N)
	{
		if (!U[i]) dfs1(i);
	}

	reverse(ALL(ord));
	FOR (i, 0, N)
	{
		U[i] = false;
	}

	int cnt = 0;
	FOR (i, 0, N)
	{
		int x = ord[i];
		if (!U[x])
		{
			dfs2(x, cnt);
			cnt++;
		}
	}
/*
	cout<<N<<endl;
	FOR (i, 0, N)
	{
		cout<<i<<": "<<endl;
		FOR (j, 0, SZ(g[i]))
		{
			int to = g[i][j];
			cout<<to<<' ';
		}
		cout<<endl;
	}*/

	//exit(0);

	FOR (i, 0, n)
	{
		if (C[i] == C[i+n]) return false;
	}
	return true;

}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	scanf("%d", &n);
	FOR (i, 0, n)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		A[i] = MP(x, y);
		E.PB(MP(x, i));
		E.PB(MP(y, i+n));
	}

	sort(ALL(E));


	int L = 0, R = INF;
	while(R - L > 1)
	{
		int m = (R + L) / 2;
		if (can(m)) L = m;
		else R = m;
	}

	cout<<L<<endl;

}

Submission Info

Compile Error

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

Judge Result