Submission #447243

#	Time	Username	Problem	Language	Result	Execution time	Memory
447243		alan8585	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	204 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> C;

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

void merge(int a, int b) {
    // cout << a << ' ' << b << '\n';
    a = find(a);
    b = find(b);
    if(a == b) return;
    C[a] = b;
}

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)
                merge(v[tr].id, now);
            tv[i] = v[tr];
            tr++;
        }
    }
    for(int i = l; i <= r; i++)
        v[i] = tv[i];
}

bool is_vali() {
    sort(ALL(v));
    stack<int> st1, st2;
    for(datas &i : v) {
        while(!st1.empty() && st1.top() < i.x)
            st1.pop();
        while(!st2.empty() && st2.top() < i.x)
            st2.pop();
        if(st1.empty() || st1.top() > i.y)
            st1.push(i.y);
        else if(st2.empty() || st2.top() > i.y)
            st2.push(i.y);
        else
            return 0;
    }
    return 1;
}

int main() {Tie
    int n;
    cin >> n;
    v.resize(n), tv.resize(n), C.resize(n);
    for(int i = 0; i < n; i++) {
        C[i] = i;
        cin >> v[i].x >> v[i].y;
        v[i].id = i;
    }
    ori = v;
    if(!is_vali()) {
        cout << "0\n";
        return 0;
    }
    v = ori;
    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;
        ori[i].x = n * 2 + 1 - ori[i].x;
        ori[i].y = n * 2 + 1 - ori[i].y;
    }
    sort(ALL(v));
    // reverse(ALL(v));
    merge_sort(0, n - 1);
    int ans = 1;
    // for(int i = 0; i < n; i++) cout << C[i] << " \n"[i == n - 1];
    for(int i = 0; i < n; i++)
        if(C[i] == i)
            ans = (ans << 1) % 100000007;
    cout << ans << '\n';
}

Compilation message (stderr)

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

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