Submission #1213896

#TimeUsernameProblemLanguageResultExecution timeMemory
1213896VMaksimoski008Port Facility (JOI17_port_facility)C++20
10 / 100
29 ms24388 KiB
#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 N = 1e6 + 5;

ll ans = 1;
int n, col[N], l[N], r[N];
vector<int> g[N];

void dfs(int u, int c) {
    col[u] = c;
    for(int v : g[u]) {
        if(col[v]) {
            if(col[v] == c) ans = 0;
            continue;
        }
        dfs(v, 3^c);
    }
}

signed main() {
    cin >> n;   
    int cnt = 0;
    for(int i=1; i<=n; i++) cin >> l[i] >> r[i];

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(l[i] < l[j] && r[i] < r[j] && l[j] < r[i]) {
                cnt++;
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    for(int i=1; i<=n; i++) {
        if(col[i]) continue;
        dfs(i, 1);
        ans = ans * 2 % mod;
    }

    assert(cnt <= 20*n);
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...