Submission #1339825

#TimeUsernameProblemLanguageResultExecution timeMemory
1339825i_love_springPort Facility (JOI17_port_facility)C++20
22 / 100
6090 ms30952 KiB
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;
const int mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vector<ar<int, 3>> a(n);
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {l, r, i};
    }
    
    sort(a.begin(), a.end());
    vector<vector<int>> g(n);
    for (auto [l, r, u] : a) 
        for (auto [l1, r1, v] : a)
            if (l <= l1 && l1 <= r && r <= r1 && u != v)
                g[u].push_back(v), g[v].push_back(u);

    int cnt = 0;
    int ok = 1;
    vector<int> col(n, -1);
    function<void(int, int)> dfs = [&](int u, int c) {
        if (col[u] != -1)  {
            ok &= (col[u] == c);
            return;
        }

        col[u] = c;
        for (int v : g[u]) {
            dfs(v, !c);
        }
    };

    for (int i = 0; i < n;i++) {
        if (col[i] == -1) {
            cnt++;
            dfs(i, 0);
        }
    }     
    if (!ok)    
        return (void)(cout << 0);
    ll ans = 1;
    for (int i = 0; i < cnt;i++) 
        ans = (ans * 2ll) % mod;
    
    cout << ans;

}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...