Submission #447265

#	Time	Username	Problem	Language	Result	Execution time	Memory
447265		alan8585	Port Facility (JOI17_port_facility)	C++14	78 / 100	6090 ms	407140 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, id;
    bool operator<(const datas &a) {
        return x < a.x;
    }
};

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

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(a > b) swap(a, b);
    C[b] = a;
}

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 && v[tl].y < v[tr].y)) {
            if(now == -1 || (ori[now].y < v[tl].y)) {
                now = v[tl].id;
            }
            tv[i] = v[tl];
            tl++;
        } else {
            if(now != -1 && v[tr].x < ori[now].y) {
                e[v[tr].id].pb(now);
                e[now].pb(v[tr].id);
                merge(v[tr].id, now + n);
                merge(now, v[tr].id + n);
            }
            tv[i] = v[tr];
            tr++;
        }
    }
    for(int i = l; i <= r; i++)
        v[i] = tv[i];
}

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

int main() {Tie
    cin >> n;
    v.resize(n), tv.resize(n), C.resize(n * 2);
    for(int i = 0; i < n; i++) {
        cin >> v[i].x >> v[i].y;
        v[i].id = i;
    }
    for(int i = 0; i < n * 2; i++)
        C[i] = i;
    ori = v;
    sort(ALL(v));
    merge_sort(0, n - 1);
    for(int i = 0; i < n; i++) {
        v[i].x = n * 2 + 1 - v[i].x;
        v[i].y = n * 2 + 1 - v[i].y;
        swap(v[i].x, v[i].y);
        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);
    }
    sort(ALL(v));
    merge_sort(0, n - 1);
    int ans = 1;
    // vector<vector<int>> con(n * 2);
    // for(int i = 0; i < n * 2; i++)
    //     cout << find(i) << ' ';
    // cout << '\n';
    for(int i = 0; i < n; i++) {
        if(vis[i]) continue;
        lv.clear();
        rv.clear();
        dfs(i, 1);

        sort(ALL(lv));
        int mx = -1;
        for(datas i : lv) {
            if(i.y > mx && mx > i.x)
                ans = 0;
            mx = max(mx, i.y);
        }

        sort(ALL(rv));
        mx = -1;
        for(datas i : rv) {
            if(i.y > mx && mx > i.x)
                ans = 0;
            mx = max(mx, i.y);
        }
    }
    for(int i = 0; i < n; i++)
        if(find(i) == find(i + n))
            ans = 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:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     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: 0 / 22