Submission #1155876

#TimeUsernameProblemLanguageResultExecution timeMemory
1155876anmattroiPort Facility (JOI17_port_facility)C++17
22 / 100
6091 ms40004 KiB
#include <bits/stdc++.h>
#define maxn 1000005
#define fi first
#define se second

using namespace std;
using ii = pair<int, int>;

constexpr int mod = 1000000007;

int n;
ii a[maxn];
vector<int> adj[maxn];
int cl[maxn];

void dfs(int u) {
    for (int v : adj[u])
    if (!cl[v]) {
        cl[v] = 3 - cl[u];
        dfs(v);
    } else if (cl[v] == cl[u]) {cout << 0; exit(0);}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++) if (a[i].se > a[j].fi && a[i].se < a[j].se) {
            adj[i].emplace_back(j);
            adj[j].emplace_back(i);
        }

    int slt = 0;
    for (int i = 1; i <= n; i++) if (!cl[i]) {
        ++slt;
        cl[i] = 1;
        dfs(i);
    }
    int ans = 1;
    while (slt--) ans = ans * 2 % mod;
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...