Submission #1197409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197409		og_matveychick1	Port Facility (JOI17_port_facility)	C++20	22 / 100	6097 ms	56388 KiB

port_facility

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

const ll N = 1e6 + 5, mod = 1e9 + 7;

ll n, l[N], r[N], used[N], fl;
vll g[N];

void dfs(ll v) {
    for (auto x: g[v]) {
        if (used[x]) {
            if (used[x] == used[v]) fl = 0;
        } else used[x] = 3 - used[v], dfs(x);
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> l[i] >> r[i];
    for (ll i = 0; i < n; i++) {
        for (ll j = i + 1; j < n; j++) {
            if (l[i] < l[j]) {
                if (r[i] > l[j] && r[i] < r[j]) g[i].push_back(j), g[j].push_back(i);
            } else {
                if (r[j] > l[i] && r[j] < r[i]) g[i].push_back(j), g[j].push_back(i);
            }
        }
    }
    ll ans = 1;
    for (ll i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = 1;
        fl = 1;
        dfs(i);
        ans = (ans * fl * 2) % mod;
    }
    cout << ans;
}

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