Submission #1062369

#TimeUsernameProblemLanguageResultExecution timeMemory
1062369vjudge1Port Facility (JOI17_port_facility)C++17
0 / 100
10 ms44380 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const int N = 1000001;
ll pw[N];
int col[N], l[N], r[N], b[2 * N];
int odd[2 * N], even[2 * N];
void update(int v, int w, int p) {
    if (!p) for (int i = v;i < 2 * N - 1;i += i & -i) odd[i] += w;
    else for (int i = v;i < 2 * N - 1;i += i & -i) even[i] += w;
}
int query(int v, int p) {
    int ans = 0;
    if (!p) for (int i = v;i > 0;i -= i & -i) ans += odd[i];
    else for (int i = v;i > 0;i -= i & -i) ans += even[i];
    return ans;
}
vector<int> adj[N];
bool dfs(int v, int c = 1) {
    if (col[v]) return c == col[v];
    col[v] = c;
    for (auto& x : adj[v]) {
        if (!dfs(x, 3 - c)) return false;
    }
    return true;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    pw[0] = 1;
    for (int i = 1;i <= 1000000;i++) pw[i] = pw[i - 1] * 2 % MOD;
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> l[i] >> r[i];
        b[r[i]] = l[i];
    }
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            int ii = i, jj = j;
            if (l[i] > l[j]) swap(ii, jj);
            if (l[jj] < r[ii] && r[ii] < r[jj]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        if (!col[i]) {
            if (!dfs(i)) {
                cout << 0 << '\n';
                return 0;
            }
        }
    }
    int cnt = 0;
    for (int i = 1;i <= 2 * n;i++) {
        if (!b[i]) continue;
        if (!query(b[i], 0)) cnt++;
        update(b[i], 1, 0);
        update(i + 1, -1, 0);
    }
    cout << pw[cnt] << '\n';
    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...