제출 #592375

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

port_facility

#include <bits/stdc++.h>

#define FOR(i, x, y)    for(int i = x; i < y; i++) 
#define F0R(i, y)       FOR(i, 0, y)
#define ROF(i, x, y)    for(int i = y - 1; i >= x; i--)
#define R0F(i, y)       ROF(i, 0, y)

#define WTF             cout << "WTF" << endl

#define ALL(x)          x.begin(), x.end()
#define RALL(x)         x.rbegin(), x.rend();

#define IOS             ios_base::sync_with_stdio(0); cin.tie(0)
#define F               first
#define S               second
#define pb              push_back

using namespace std;

typedef long long LL;

typedef pair<int, int>  PII;
typedef pair<LL, LL>    PLL;

typedef vector<int>     VI;
typedef vector<LL>      VLL;
typedef vector<PII>     VPII;
typedef vector<PLL>     VPLL;

const int N = 1e6 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

#define lc now << 1
#define rc now << 1 | 1

int n, f[N << 1];
bool vis[N], comp[N];
PII ns[N];
set<PII> tree[N << 2];
queue<int> keep;
stack<int> dr;

void add(int place, PII x, int now = 1, int ls = 0, int rs = (n << 1) - 1) {
    tree[now].insert(x);
    if (ls == rs) return;

    int mid = (ls + rs) >> 1;
    if (place <= mid) add(place, x, lc, ls, mid);
    else add(place, x, rc, mid + 1, rs);
    return;
}

void rem(int place, PII x, int now = 1, int ls = 0, int rs = (n << 1) - 1) {
    tree[now].erase(x);
    if (ls == rs) return;

    int mid = (ls + rs) >> 1;
    if (place <= mid) rem(place, x, lc, ls, mid);
    else rem(place, x, rc, mid + 1, rs);
    return;
}

void init() {
    cin >> n;
    F0R(i, n) {
        cin >> ns[i].F >> ns[i].S;
        ns[i].F--; ns[i].S--;
        add(ns[i].F, {ns[i].S, i});
    }

    return;
}

void getEdge(int lq, int rq, int now = 1, int ls = 0, int rs = (n << 1) - 1) {
    if (rq < lq || rq < ls || rs < lq) return;
    if (lq <= ls && rs <= rq) {
        if (tree[now].empty()) return;
        for(PII on = *(--tree[now].end()); ; on = *(--tree[now].lower_bound(on))) {
            if (on.F <= rq) break;
            dr.push(on.S);
            if (on == *tree[now].begin()) break;
        }

        return;
    }

    int mid = (ls + rs) >> 1;
    getEdge(lq, rq, lc, ls, mid);
    getEdge(lq, rq, rc, mid + 1, rs);

    return;
}

void bfs(int now) {
    vis[now] = 1;
    comp[now] = 0;
    rem(ns[now].F, {ns[now].S, now});
    keep.push(now);

    while(!keep.empty()) {
        int on = keep.front();
        keep.pop();
        getEdge(ns[on].F, ns[on].S);

        while(!dr.empty()) {
            int x = dr.top(); dr.pop();

            comp[x] = 1 ^ comp[on];
            vis[x] = 1;
            rem(ns[x].F, {ns[x].S, x});
            keep.push(x);
        }
    }

    return;
}

bool check() {
    memset(f, 0, sizeof f);
    F0R(i, n) if (!comp[i]) f[ ns[i].F ] = (i + 1), f[ ns[i].S ] = -(i + 1);

    stack<int> st;
    F0R(i, (n << 1)) if (f[i]) {
        if (f[i] > 0) st.push(f[i]);
        else {
            if (st.empty() || st.top() != -f[i]) return 0;
            st.pop();
        }
    }

    memset(f, 0, sizeof f);
    F0R(i, n) if (comp[i]) f[ ns[i].F ] = (i + 1), f[ ns[i].S ] = -(i + 1);

    while(!st.empty()) st.pop();
    F0R(i, (n << 1)) if (f[i]) {
        if (f[i] > 0) st.push(f[i]);
        else {
            if (st.empty() || st.top() != -f[i]) return 0;
            st.pop();
        }
    }
    return 1;
}

int main() {
    IOS;

    init();

    int ans = 1;
    F0R(i, n) if (!vis[i]) {
        bfs(i);
        ans = (ans << 1) % MOD;
    }

    cout << (check() ? ans : 0);
}

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