Submission #1294081

#TimeUsernameProblemLanguageResultExecution timeMemory
1294081pvb.tunglamPort Facility (JOI17_port_facility)C++20
0 / 100
105 ms250928 KiB
#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 {
	pair <int, int> it[16000036];
	SegmentTree(){};
	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 (l > v || r < u) return {-1e9, 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, {-1e9, 0});
	segTreeMin.update(1, 1, 2*N, a[u].second, {-1e9, 0});
	while (true) {
		int v = segTreeMax.getPos(1, 1, 2 * N, a[u].first + 1, a[u].second - 1).second;
		if (a[v].second <= a[u].second || !v) 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 (a[v].first >= a[u].first || !v) 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] = event[a[i].second] = i;
		}
		else event[a[i].first] = event[a[i].second] = 0;
	}
	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;
	}
	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
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...