Submission #986816

#	Time	Username	Problem	Language	Result	Execution time	Memory
986816		alextodoran	Port Facility (JOI17_port_facility)	C++17	100 / 100	5696 ms	771316 KiB

port_facility

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 1000000;
const int MOD = (int) 1e9 + 7;

int N;
int L[N_MAX + 2], R[N_MAX + 2];

struct SegInfo {
    vector <int> byL, byR;
};
SegInfo seg_tree[N_MAX * 8 + 2];

void add_L (int node, int l, int r, int i) {
    seg_tree[node].byL.push_back(i);
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    if (R[i] <= mid) {
        add_L(left, l, mid, i);
    } else {
        add_L(right, mid + 1, r, i);
    }
}
void add_L (int i) {
    add_L(1, 1, N * 2, i);
}
void add_R (int node, int l, int r, int i) {
    seg_tree[node].byR.push_back(i);
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    if (L[i] <= mid) {
        add_R(left, l, mid, i);
    } else {
        add_R(right, mid + 1, r, i);
    }
}
void add_R (int i) {
    add_R(1, 1, N * 2, i);
}

int order[N_MAX + 2];

int color[N_MAX + 2];

int find_L (int node, int l, int r, int i) {
    if (L[i] <= l && r <= R[i]) {
        while (seg_tree[node].byL.empty() == false && color[seg_tree[node].byL.back()] != 0) {
            seg_tree[node].byL.pop_back();
        }
        if (seg_tree[node].byL.empty() == false && L[seg_tree[node].byL.back()] < L[i]) {
            return seg_tree[node].byL.back();
        } else {
            return 0;
        }
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    if (L[i] <= mid) {
        int j = find_L(left, l, mid, i);
        if (j != 0) {
            return j;
        }
    }
    if (mid + 1 <= R[i]) {
        int j = find_L(right, mid + 1, r, i);
        if (j != 0) {
            return j;
        }
    }
    return 0;
}
int find_L (int i) {
    return find_L(1, 1, N * 2, i);
}
int find_R (int node, int l, int r, int i) {
    if (L[i] <= l && r <= R[i]) {
        while (seg_tree[node].byR.empty() == false && color[seg_tree[node].byR.back()] != 0) {
            seg_tree[node].byR.pop_back();
        }
        if (seg_tree[node].byR.empty() == false && R[i] < R[seg_tree[node].byR.back()]) {
            return seg_tree[node].byR.back();
        } else {
            return 0;
        }
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    if (L[i] <= mid) {
        int j = find_R(left, l, mid, i);
        if (j != 0) {
            return j;
        }
    }
    if (mid + 1 <= R[i]) {
        int j = find_R(right, mid + 1, r, i);
        if (j != 0) {
            return j;
        }
    }
    return 0;
}
int find_R (int i) {
    return find_R(1, 1, N * 2, i);
}

void dfs (int i) {
    int j;
    while (j = find_L(i)) {
        color[j] = 3 - color[i];
        dfs(j);
    }
    while (j = find_R(i)) {
        color[j] = 3 - color[i];
        dfs(j);
    }
}

int which[N_MAX * 2 + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> L[i] >> R[i];
    }
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
        return L[i] > L[j];
    });
    for (int i = 1; i <= N; i++) {
        add_L(order[i]);
    }
    sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
        return R[i] < R[j];
    });
    for (int i = 1; i <= N; i++) {
        add_R(order[i]);
    }
    int answer = 1;
    for (int i = 1; i <= N; i++) {
        if (color[i] == 0) {
            color[i] = 1;
            dfs(i);
            answer = answer * 2 % MOD;
        }
    }
    for (int i = 1; i <= N; i++) {
        which[L[i]] = which[R[i]] = i;
    }
    vector <int> st[3];
    for (int i = 1; i <= N * 2; i++) {
        if (i == L[which[i]]) {
            st[color[which[i]]].push_back(which[i]);
        } else {
            if (st[color[which[i]]].back() != which[i]) {
                cout << 0 << "\n";
                exit(0);
            }
            st[color[which[i]]].pop_back();
        }
    }
    cout << answer << "\n";

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void dfs(int)':
port_facility.cpp:126:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  126 |     while (j = find_L(i)) {
      |            ~~^~~~~~~~~~~
port_facility.cpp:130:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  130 |     while (j = find_R(i)) {
      |            ~~^~~~~~~~~~~

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