제출 #1062369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062369		vjudge1	Port Facility (JOI17_port_facility)	C++17	0 / 100	10 ms	44380 KiB

port_facility

#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;
}

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