Submission #447279

#	Time	Username	Problem	Language	Result	Execution time	Memory
447279		alan8585	Port Facility (JOI17_port_facility)	C++14	100 / 100	3570 ms	183752 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;
}

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

void merge_sort(int l, int r) {
    if(l == r) return;
    int m = l + r >> 1, tl = l, tr = m + 1, now = -1;
    merge_sort(l, m);
    merge_sort(m + 1, r);
    for(int i = l; i <= r; i++) {
        if(tr > r || (tl <= m && ori[v[tl]].y < ori[v[tr]].y)) {
            if(now == -1 || (ori[now].y < ori[v[tl]].y))
                now = v[tl];
            tv[i] = v[tl++];
        } else {
            if(now != -1 && ori[v[tr]].x < ori[now].y) {
                if(!(merge(v[tr], now + n) & merge(now, v[tr] + n))) {
                    e[v[tr]].pb(now);
                    e[now].pb(v[tr]);
                }
            }
            tv[i] = v[tr++];
        }
    }
    // for(int i = l; i <= r; i++)
    //     v[i] = tv[i];
    memcpy(v + l, tv + l, sizeof(int) * (r - l + 1));
}

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';
}

Compilation message (stderr)

port_facility.cpp: In function 'void merge_sort(int, int)':
port_facility.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int m = l + r >> 1, tl = l, tr = m + 1, now = -1;
      |             ~~^~~

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