Submission #1294083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294083		pvb.tunglam	Port Facility (JOI17_port_facility)	C++20	100 / 100	2721 ms	337004 KiB

port_facility

#include <bits/stdc++.h>
#define pw2(i) (1LL << (i))
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;

/*------------- I alone decide my fate ! -------------*/

const ll MOD = 1e9 + 7;
int N, color[1000009];
pair <int, int> a[1000009];

struct SegmentTree {
    vector<pair<int,int>> it;
    SegmentTree(){}
    void init(int size) {
        it.assign(4 * size + 5, {-1000000000, 0});
    }
    void update(int id, int l, int r, int pos, pair<int,int> val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            it[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id*2, l, mid, pos, val);
        update(id*2 + 1, mid + 1, r, pos, val);
        it[id] = max(it[id*2], it[id*2 + 1]);
    }
    pair<int,int> getPos(int id, int l, int r, int u, int v) {
        if (u > v) return {-1000000000, 0};
        if (l > v || r < u) return {-1000000000, 0};
        if (l >= u && r <= v) {
            return it[id];
        }
        int mid = (l + r) >> 1;
        return max(getPos(id*2, l, mid, u, v), getPos(id*2 + 1, mid + 1, r, u , v));
    }
};
SegmentTree segTreeMax, segTreeMin;

void DFS(int u, int col) {
    color[u] = col;
    segTreeMax.update(1, 1, 2*N, a[u].first, {-1000000000, 0});
    segTreeMin.update(1, 1, 2*N, a[u].second, {-1000000000, 0});

    while (true) {
        int v = segTreeMax.getPos(1, 1, 2 * N, a[u].first + 1, a[u].second - 1).second;
        if (!v || a[v].second <= a[u].second) break;
        DFS(v, col ^ 1);
    }
    while (true) {
        int v = segTreeMin.getPos(1, 1, 2 * N, a[u].first + 1, a[u].second - 1).second;
        if (!v || a[v].first >= a[u].first) break;
        DFS(v, col ^ 1);
    }
}

int st[1000009], event[2000009];
bool check(int tp) {
    for (int i = 1; i <= 2 * N; ++i) event[i] = 0;

    for (int i = 1; i <= N; i ++) {
        if (color[i] == tp) {
            event[a[i].first] = i;
            event[a[i].second] = i;
        }
    }
    int top = 0;
    for (int i = 1; i <= 2 * N; i ++) {
        if (event[i]) {
            if (top > 0 && st[top] == event[i]) top --;
            else st[++top] = event[i];
        }
    }
    return (top == 0);
}

void solve() {
	cin >> N;
	for (int i = 1; i <= N; i ++) {
		cin >> a[i].first >> a[i].second;
	}
	segTreeMax.init(2 * N);
    segTreeMin.init(2 * N);
	for (int i = 1; i <= N; i ++) {
		segTreeMax.update(1, 1, 2*N, a[i].first, {a[i].second, i});
		segTreeMin.update(1, 1, 2*N, a[i].second, {-a[i].first, i});
	}
	for (int i = 1; i <= N; i ++) color[i] = -1;
	ll res = 1;
	for (int i = 1; i <= N; i ++) {
		if (color[i] == -1) {
			DFS(i, 0);
			res = (res * 2) % MOD;
		}
	} 
	if(!check(1) || !check(0)) cout << 0;
	else cout << res;
 
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);
	solve();
	return 0;
}

/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Can't wake up? Wake me up inside
*/

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