Submission #447277

#	Time	Username	Problem	Language	Result	Execution time	Memory
447277		alan8585	Port Facility (JOI17_port_facility)	C++14	0 / 100	15 ms	23756 KiB

port_facility

#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

struct datas {
    int x, y;
    bool operator<(const datas &a) {
        return x < a.x;
    }
};

vector<datas> ori;
vector<int> e[1000100];
int n, v[1000100], tv[1000100], sz[2000100], C[2000100];

int find(int a) {
    if(C[a] != a)
        return C[a] = find(C[a]);
    return a;
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if(a == b) return;
    if(sz[a] < sz[b])
        swap(a, b);
    // if(a > b) swap(a, b);
    sz[a] += sz[b];
    C[b] = a;
}


map<int, int> m;
void merge_sort(int l, int r) {
    m.clear();
    for(int i = 0; i < n; i++) {
        auto p = m.lower_bound(ori[v[i]].y);
        if(p != m.begin()) {
            p--;
            if(ori[p -> S].y < ori[v[i]].x)
                continue;
            e[p -> S].pb(v[i]);
            e[v[i]].pb(p -> S);
            merge(p -> S, v[i] + n);
            merge(v[i], p -> S + n);
        }
        m[ori[v[i]].y] = v[i];
    }
}

bitset<1000100> vis;
vector<int> lv, rv;
void dfs(int a, int c) {
    vis[a] = 1;
    if(c == 1)
        lv.pb(a);
    else
        rv.pb(a);
    for(int i : e[a])
        if(!vis[i])
            dfs(i, 3 - c);
}

bool f(int a, int b) {
    return ori[a].x < ori[b].x;
}

int main() {Tie
    cin >> n;
    ori.resize(n);
    for(int i = 0; i < n; i++)
        cin >> ori[i].x >> ori[i].y;
    for(int i = 0; i < n * 2; i++)
        C[i] = i, sz[i] = 1;

    for(int i = 0; i < n; i++)
        v[i] = i;
    sort(v, v + n, f);
    merge_sort(0, n - 1);

    for(int i = 0; i < n; i++) {
        ori[i].x = n * 2 + 1 - ori[i].x;
        ori[i].y = n * 2 + 1 - ori[i].y;
        swap(ori[i].x, ori[i].y);
    }

    for(int i = 0; i < n; i++)
        v[i] = i;
    sort(v, v + n, f);
    merge_sort(0, n - 1);

    int ans = 1;
    for(int i = 0; i < n; i++) {
        if(vis[i]) continue;
        lv.clear();
        rv.clear();
        dfs(i, 1);

        sort(ALL(lv), f);
        int mx = -1;
        for(int i : lv) {
            if(ori[i].y > mx && mx > ori[i].x) {
                cout << "0\n";
                return 0;
            }
            mx = max(mx, ori[i].y);
        }

        sort(ALL(rv), f);
        mx = -1;
        for(int i : rv) {
            if(ori[i].y > mx && mx > ori[i].x) {
                cout << "0\n";
                return 0;
            }
            mx = max(mx, ori[i].y);
        }
    }
    for(int i = 0; i < n; i++)
        if(find(i) == find(i + n)) {
            cout << "0\n";
            return 0;
        }
    int tmp = 0;
    for(int i = 0; i < 2 * n; i++)
        if(find(i) == i)
            tmp++;
    tmp >>= 1;
    for(int i = 0; i < tmp; i++)
        ans = (ans << 1) % 1000000007;
    cout << ans << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22