제출 #1142895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142895		VMaksimoski008	Port Facility (JOI17_port_facility)	C++20	0 / 100	1 ms	324 KiB

port_facility

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

struct union_find {
    int n;
    vector<int> par;
    union_find(int _n) : n(_n), par(n+1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    void uni(int a, int b) {
        par[find(a)] = find(b);
    }
};

bool edge(ar<int, 2> a, ar<int, 2> b) {
    if(b[0] < a[1] && a[1] < b[1]) return 1;
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n; cin >> n;
    vector<ar<int, 2> > a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1];
    sort(a.begin()+1, a.end());

    bool ok = 1;
    vector<ar<int, 2> > t(2*n+1);
    
    for(int i=1; i<=n; i++) {
        t[a[i][0]] = { i, 1 };
        t[a[i][1]] = { i, -1 };
    }

    stack<int> st[2];
    for(int i=1; i<=2*n&&ok; i++) {
        if(t[i][1] == 1) {
            if(st[0].empty()) {
                st[0].push(i);
            } else if(st[1].empty()) {
                st[1].push(i);
            } else {
                if(!edge(a[st[0].top()], a[i])) st[0].push(i);
                else if(!edge(a[st[1].top()], a[i])) st[1].push(i);
                else ok = 0;
            }
        } else {
            if(!st[0].empty() && st[0].top() == t[i][0]) st[0].pop();
            else st[1].pop();
        }
    }

    if(!ok) {
        assert(ok);
        cout << 0 << '\n';
        return 0;
    }

    ll ans = 1;
    union_find dsu(n);

    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            if(edge(a[i], a[j])) dsu.uni(i, j);

    for(int i=1; i<=n; i++)
        if(i == dsu.find(i)) ans = (ans * 2) % mod;
    cout << ans << '\n';
}

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