Submission #1118887

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, cnt, nodes;
int x[10000], y[10000];
PII p[20000];
vector<int> g[320000], rev[320000];
int ord[320000], ordc;
int cmp[320000];
bool used[320000];

void dfs1(int v) {
    used[v] = true;
    for (int to : g[v]) {
        if (!used[to]) {
            dfs1(to);
        }
    }
    ord[ordc++] = v;
}

int col;
void dfs2(int v) {
    cmp[v] = col;
    for (int to : rev[v]) {
        if (cmp[to] == -1) {
            dfs2(to);
        }
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    forn(i, n) scanf("%d%d", x + i, y + i);
    cnt = 2 * n;
    forn(i, n) {
        p[i] = mp(x[i], 2 * i);
        p[n + i] = mp(y[i], 2 * i + 1);
    }
    sort(p, p + cnt);
//    forn(i, cnt) cerr << p[i].first << ' ' << p[i].second << endl;
//    cerr << "---\n";
    nodes = 16 * cnt;
    forn(i, cnt) {
        for (int j = 0; i + (2 << j) <= cnt; ++j) {
            if (j == 0) {
                g[cnt + i].pb(p[i].second ^ 1);
                g[cnt + i].pb(p[i + 1].second ^ 1);
            } else {
                g[(j + 1) * cnt + i].pb(j * cnt + i);
                g[(j + 1) * cnt + i].pb(j * cnt + i + (1 << j));
            }
        }
    }
//    forn(i, nodes) for (int to : g[i]) {
//        cerr << i << ' ' << to << endl;
//    }
//    cerr << "---" << endl;
    int lo = 0, hi = int(1e9);
    while (lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        forn(i, cnt) {
            g[i].clear();
        }
        int j = 0;
        forn(i, cnt - 1) {
            while (j < cnt - 1 && p[j + 1].first - p[i].first < mid) {
                ++j;
            }
            if (j > i) {
                int from = i + 1;
                int to = j;
                int cnt = j - i;
                int sz = 0;
                while ((2 << sz) < cnt) {
                    ++sz;
                }
                if (sz == 0) {
                    g[p[i].second].pb(p[from].second ^ 1);
                    if (cnt == 2) {
                        g[p[i].second].pb(p[from + 1].second ^ 1);
                    }
                } else {
                    g[p[i].second].pb(sz * ::cnt + from);
                    g[p[i].second].pb(sz * ::cnt + to + 1 - (1 << sz));
                }
            }
        }
        j = cnt - 1;
        for (int i = cnt - 1; i >= 0; --i) {
            while (j > 0 && p[i].first - p[j - 1].first < mid) {
                --j;
            }
            if (j < i) {
                int from = j;
                int to = i - 1;
                int cnt = i - j;
                int sz = 0;
                while ((2 << sz) < cnt) {
                    ++sz;
                }
                if (sz == 0) {
                    g[p[i].second].pb(p[from].second ^ 1);
                    if (cnt == 2) {
                        g[p[i].second].pb(p[from + 1].second ^ 1);
                    }
                } else {
                    g[p[i].second].pb(sz * ::cnt + from);
                    g[p[i].second].pb(sz * ::cnt + to + 1 - (1 << sz));
                }
            }
        }
        forn(i, nodes) {
            rev[i].clear();
        }
        forn(i, nodes) for (int to : g[i]) {
//            if (mid == 3) cerr << i << ' ' << to << endl;
            rev[to].pb(i);
        }
        forn(i, nodes) used[i] = false;
        ordc = 0;
        forn(i, nodes) if (!used[i]) {
            dfs1(i);
        }
        forn(i, nodes) cmp[i] = -1;
        col = 0;
        forn(i, nodes) {
            int v = ord[nodes - 1 - i];
            if (cmp[v] == -1) {
                dfs2(v);
                ++col;
            }
        }
        bool ok = true;
        forn(i, n) if (cmp[2 * i] == cmp[2 * i + 1]) {
            ok = false;
            break;
        }
        if (ok) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    cout << lo << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:42:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     forn(i, n) scanf("%d%d", x + i, y + i);
                                           ^

Judge Result