Submission #1369814

---

Source Code Expand

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 15;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

inline int ch(int n) {
	if (n <= 2 * IT_MAX) return n + 2 * IT_MAX;
	else return n - 2 * IT_MAX;
}

ll in[200050];
int u[400050];
vector <int> conn[140000];
vector <int> rconn[140000];
void epush(int a, int b) {
	conn[ch(a)].push_back(b);
	conn[ch(b)].push_back(a);
	rconn[a].push_back(ch(b));
	rconn[b].push_back(ch(a));
}
void getv(int st, int en, int S, int E, int n, vector<int>& Vu) {
	if (st > en) return;
	if (st == S && en == E) {
		Vu.push_back(u[n]);
		return;
	}
	int M = (S + E) / 2;
	getv(st, min(M, en), S, M, 2 * n, Vu);
	getv(max(M + 1, st), en, M + 1, E, 2 * n + 1, Vu);
}

bool dchk[140000];
int G[140000];
vector <int> Vstk;
void DFS1(int n) {
	dchk[n] = true;
	for (auto it : conn[n]) if (!dchk[it]) DFS1(it);
	Vstk.push_back(n);
}
void DFS2(int n, int g) {
	G[n] = g;
	for (auto it : rconn[n]) if (!G[it]) DFS2(it, g);
}

int main() {
	int N, i, j, k;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%lld %lld", &in[i], &in[N + i]);

	for (i = 1; i <= 2 * N; i++) u[i] = i;
	sort(u + 1, u + 2 * N + 1, [](int a, int b) {
		return in[a] < in[b];
	});
	for (i = 1; i <= 2 * N; i++) u[IT_MAX + i - 1] = u[i];
	for (i = 2 * N + 1; i <= IT_MAX; i++) u[IT_MAX + i - 1] = i;

	int st = 1, en = INF, mi, rv = 0;
	while (st <= en) {
		mi = (st + en) / 2;
		for (i = IT_MAX - 1; i >= 1; i--) {
			u[i] = 2 * IT_MAX - i;
			epush(u[i], ch(u[2 * i]));
			epush(u[i], ch(u[2 * i + 1]));
		}
		for (i = 1; i <= N; i++) {
			epush(i, N + i);
			epush(ch(i), ch(N + i));
		}

		vector <int> Vu;
		int p = 1;
		for (i = 1; i <= 2 * N; i++) {
			Vu.clear();
			while (p < 2 * N) {
				if (in[u[IT_MAX - 1 + p + 1]] >= in[u[IT_MAX - 1 + i]] + mi) break;
				p++;
			}
			getv(i + 1, p, 1, IT_MAX, 1, Vu);
			for (auto it : Vu) epush(ch(u[IT_MAX+i-1]), ch(it));
		}

		for (i = 1; i <= 4 * IT_MAX; i++) if (!dchk[i]) DFS1(i);
		reverse(all(Vstk));
		int gc = 0;
		for (auto it : Vstk) if (!G[it]) DFS2(it, ++gc);
		for (i = 1; i <= 2 * IT_MAX; i++) if (G[i] == G[i + 2 * IT_MAX]) break;
		if (i > 2 * IT_MAX) {
			rv = mi;
			st = mi + 1;
		}
		else en = mi - 1;

		for (i = 1; i <= 4 * IT_MAX; i++) {
			dchk[i] = 0;
			G[i] = 0;
			conn[i].clear();
			rconn[i].clear();
		}
		Vstk.clear();
	}
	return !printf("%d\n", rv);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:95:65: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= N; i++) scanf("%lld %lld", &in[i], &in[N + i]);
                                                                 ^

Judge Result