Submission #1295207

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

void stronglyConnectedComponents(const vector<vector<int> >& edges, vector<int>& indexConvert,
                                 vector<vector<int> >& nodesOut, vector<vector<int> >& edgesOut)
{
    const int n = edges.size();
    vector<int> num(n, -1), low(n, -1);
    vector<bool> isStk(n, false);
    stack<int> stk;
    int cnt = -1;
    nodesOut.clear();

    for(int i=0; i<n; ++i){
        stack<pair<int, unsigned> > arg;
        arg.push(make_pair(i, 0));

        while(!arg.empty()){
            int v = arg.top().first;
            unsigned j = arg.top().second;
            arg.pop();

            if(j == 0){
                if(num[v] != -1)
                    continue;
                num[v] = low[v] = ++ cnt;
                stk.push(v);
                isStk[v] = true;
            }
            else{
                int w = edges[v][j-1];
                if(isStk[w])
                    low[v] = min(low[v], low[w]);
            }

            if(j < edges[v].size()){
                arg.push(make_pair(v, j + 1));
                int w = edges[v][j];
                arg.push(make_pair(w, 0));
            }
            else if(low[v] == num[v]){
                nodesOut.push_back(vector<int>());
                for(;;){
                    int w = stk.top();
                    stk.pop();
                    isStk[w] = false;
                    nodesOut.back().push_back(w);
                    if(v == w)
                        break;
                }
            }
        }
    }

    reverse(nodesOut.begin(), nodesOut.end()); // DAGにするために反転させる
    const int m = nodesOut.size();
    indexConvert.resize(n);
    for(int i=0; i<m; ++i){
        for(unsigned j=0; j<nodesOut[i].size(); ++j)
            indexConvert[nodesOut[i][j]] = i;
    }
    edgesOut.assign(m, vector<int>());
    vector<set<int> > used(m);
    for(int i=0; i<n; ++i){
        for(unsigned j=0; j<edges[i].size(); ++j){
            int v = indexConvert[i];
            int w = indexConvert[edges[i][j]];
            if(v != w && used[v].find(w) == used[v].end()){
                edgesOut[v].push_back(w);
                used[v].insert(w);
            }
        }
    }
}

bool is2sat(int n, const vector<pair<int, bool> >& cs, vector<bool>& ans)
{
    vector<vector<int> > edges1(2*n);
    for(unsigned i=0; i<cs.size(); i+=2){
        int a = cs[i].first * 2 + (cs[i].second ? 0 : 1);
        int b = cs[i+1].first * 2 + (cs[i+1].second ? 0 : 1);
        edges1[a^1].push_back(b);
        edges1[b^1].push_back(a);
    }

    vector<int> indexConvert;
    vector<vector<int> > nodes, edges2;
    stronglyConnectedComponents(edges1, indexConvert, nodes, edges2);

    ans.resize(n);
    for(int i=0; i<n; ++i){
        if(indexConvert[2*i] < indexConvert[2*i+1])
            ans[i] = false;
        else if(indexConvert[2*i+1] < indexConvert[2*i])
            ans[i] = true;
        else
            return false;
    }
    return true;
}

class SegmentTree
{
private:
    int n;
    void getRangeIndex(int a, int b, int k, int l, int r, vector<int>& index){
        if(a <= l && r <= b){
            index.push_back(k);
        }
        else if(a <= r && l <= b){
            getRangeIndex(a, b, k*2+1, l, (l+r)/2, index);
            getRangeIndex(a, b, k*2+2, (l+r+1)/2, r, index);
        }
    }
public:
    SegmentTree(int n0){
        n = 1;
        while(n < n0)
            n *= 2;
    }
    int getNodeNum(){
        return 2 * n - 1;
    }
    int getLeafIndex(int a){
        return n - 1 + a;
    }
    int getParentIndex(int a){
        if(a == 0)
            return -1;
        else
            return (a - 1) / 2;
    }
    void getRangeIndex(int a, int b, vector<int>& index){
        index.clear();
        return getRangeIndex(a, b, 0, 0, n-1, index);
    }
};

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int> > flag(2*n);
    for(int i=0; i<2*n; ++i){
        cin >> flag[i].first;
        flag[i].second = i;
    }

    sort(flag.begin(), flag.end());
    vector<int> index(2*n);
    for(int i=0; i<2*n; ++i)
        index[flag[i].second] = i;

    SegmentTree st(2*n);
    int m = st.getNodeNum();

    int left = 0;
    int right = 1000000000;
    while(left < right){
        vector<pair<int, bool> > cs;
        for(int a=1; a<m; ++a){
            int b = st.getParentIndex(a);
            cs.push_back(make_pair(a, false));
            cs.push_back(make_pair(b, true));
        }
        for(int i=0; i<n; ++i){
            cs.push_back(make_pair(st.getLeafIndex(index[2*i]), true));
            cs.push_back(make_pair(st.getLeafIndex(index[2*i+1]), true));
        }

        int mid = (left + right + 1) / 2;
        int j = 0;
        int k = 0;
        for(int i=0; i<2*n; ++i){
            while(flag[i].first - flag[j].first >= mid)
                ++ j;
            while(k < 2*n && flag[k].first - flag[i].first < mid)
                ++ k;

            vector<int> v;
            st.getRangeIndex(j, i-1, v);
            for(int a : v){
                cs.push_back(make_pair(st.getLeafIndex(i), false));
                cs.push_back(make_pair(a, false));
            }
            st.getRangeIndex(i+1, k-1, v);
            for(int a : v){
                cs.push_back(make_pair(st.getLeafIndex(i), false));
                cs.push_back(make_pair(a, false));
            }
        }

        vector<bool> tmp;
        if(is2sat(m, cs, tmp))
            left = mid;
        else
            right = mid - 1;
    }

    cout << left << endl;

    return 0;
}

Submission Info

Judge Result