Submission #619185

#	Time	Username	Problem	Language	Result	Execution time	Memory
619185		Jomnoi	Port Facility (JOI17_port_facility)	C++17	100 / 100	3478 ms	198844 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_N = 1e6 + 5;
const int INF = 1e9 + 7;

int A[MAX_N], B[MAX_N];
vector <int> graph[MAX_N];
int color[MAX_N];

struct Node {
    int far, idx;

    Node() : far(-INF), idx(-INF) {}
    Node(int f, int i) : far(f), idx(i) {}
    
    Node operator+(const Node &o) const {
        if(far > o.far) {
            return Node(far, idx);
        }
        return o;
    }
}tree[8 * MAX_N];

void build(int idx, int l, int r) {
    tree[idx] = Node();
    if(l == r) {
        return;
    }

    int mid = (l + r) / 2;
    build(idx * 2, l, mid);
    build(idx * 2 + 1, mid + 1, r);
}

void update(int idx, int l, int r, int q, pair <int, int> v) {
    if(l == r) {
        if(tree[idx].far < v.first) {
            tree[idx].far = v.first;
            tree[idx].idx = v.second;
        }
        return;
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        update(idx * 2, l, mid, q, v);
    }
    else {
        update(idx * 2 + 1, mid + 1, r, q, v);
    }
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

Node query(int idx, int l, int r, int ql, int qr) {
    if(r < ql or qr < l) {
        return Node();
    }
    if(ql <= l and r <= qr) {
        return tree[idx];
    }

    int mid = (l + r) / 2;
    return query(idx * 2, l, mid, ql, qr) + query(idx * 2 + 1, mid + 1, r, ql, qr);
}

void dfs(int u, int c) {
    color[u] = c;
    for(auto v : graph[u]) {
        if(color[v] == -1) {
            dfs(v, c ^ 1);
        }
        else {
            if(color[u] == color[v]) {
                cout << 0;
                exit(0);
            }
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, S;
    cin >> N;

    vector <int> vec;
    for(int i = 1; i <= N; i++) {
        cin >> A[i] >> B[i];

        vec.push_back(A[i]);
        vec.push_back(B[i]);
    }

    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    S = vec.size();

    for(int i = 1; i <= N; i++) {
        A[i] = lower_bound(vec.begin(), vec.end(), A[i]) - vec.begin() + 1;
        B[i] = lower_bound(vec.begin(), vec.end(), B[i]) - vec.begin() + 1;
    }

    build(1, 1, S);
    for(int i = 1; i <= N; i++) {
        update(1, 1, S, A[i], make_pair(B[i], i));
    }
    for(int i = 1; i <= N; i++) {
        Node nxt = query(1, 1, S, A[i] + 1, B[i] - 1);
        if(nxt.idx != -INF and nxt.far > B[i]) {
            graph[i].push_back(nxt.idx);
            graph[nxt.idx].push_back(i);
        }
    }

    build(1, 1, S);
    for(int i = 1; i <= N; i++) {
        update(1, 1, S, B[i], make_pair(-A[i], i));
    }
    for(int i = 1; i <= N; i++) {
        Node nxt = query(1, 1, S, A[i] + 1, B[i] - 1);
        if(nxt.idx != -INF and -nxt.far < A[i]) {
            graph[i].push_back(nxt.idx);
            graph[nxt.idx].push_back(i);
        }
    }

    memset(color, -1, sizeof(color));
    int cnt_cmp = 0;
    for(int i = 1; i <= N; i++) {
        if(color[i] == -1) {
            cnt_cmp++;
            dfs(i, 0);
        }
    }

    int ans = 1;
    while(cnt_cmp--) {
        ans *= 2;
        ans %= MOD; 
    }
    cout << ans;
    return 0;
}

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