Submission #205000

#	Time	Username	Problem	Language	Result	Execution time	Memory
205000		hanagasumi	Port Facility (JOI17_port_facility)	C++17	78 / 100	6157 ms	1048576 KiB

port_facility

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
 
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll
 
using namespace std;
typedef long long ll;
typedef long double ld;

vector<vector<int>> tree;
vector<int> p;
vector<int> sz;
vector<vector<int>> g;
vector<int> color;
vector<int> used;


int N = 1;

int findp(int v) {
	if(p[v] == v)
		return v;
	p[v] = findp(p[v]);
	return p[v];
}

void merge(int a, int b) {
	a = findp(a), b = findp(b);
	if(a == b) 
		return;
	if(sz[a] < sz[b]) 
		swap(a, b);
	sz[a] += sz[b];
	p[b] = a;
}

void add(int v, int val) {
	if(v == 0) 
		return;
	tree[v].pb(val);
	add(v / 2, val);
}

void merge2(int v, int l, int r, int vl, int vr, int val) {
	if(vr <= l || r <= vl) 
		return;
	if(vl <= l && r <= vr) {
		if(len(tree[v]) == 0)
			return;
		int x = tree[v][0];
		for (auto y : tree[v]) {
			g[y].pb(val);
			g[val].pb(y);
			merge(x, y);
		}
		merge(x, val);
		x = tree[v][0];
		tree[v].clear();
		tree[v].pb(x);
		return;
	}
	int m = (l + r) / 2;
	merge2(v * 2, l, m, vl, vr, val);
	merge2(v * 2 + 1, m, r, vl, vr, val);
}

void dfs(int v, int col) {
	used[v] = 1;
	color[v] = col;
	for (auto x : g[v]) {
		if(used[x]) 
			continue;
		dfs(x, 3 - col);
	}
}

bool ch(vector<pair<int, int>>& a) {
	vector<int> st;
	vector<pair<int, int>> scan;
	for (int i = 0; i < len(a); i++) {
		scan.pb({a[i].ft, a[i].sc});
		scan.pb({a[i].sc, -1});
	}
	sort(scan.begin(), scan.end());
	for (auto x : scan) {
		if(x.sc >= 0) {
			if(len(st) == 0) {
				st.pb(x.sc);
				continue;
			}
			if(st.back() < x.sc) 
				return 0;
			st.pb(x.sc);
		}
		else {
			if(st.back() != x.ft) 
				return 0;
			st.pop_back();
		}
	}
	return 1;
}

ll mod = 1e9 + 7;

signed main() {
	#ifdef PC 
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	while(N < (2 * n + 1)) 
		N *= 2;
	tree = vector<vector<int>> (2 * N);
	p = vector<int> (N);
	sz = vector<int> (N, 1);
	vector<int> was;
	unordered_map<int, int> num;
	vector<pair<int, int>> have(n);
	vector<int> wasc(n + 1, 0);
	g = vector<vector<int>> (n + 1);
	color = vector<int> (n + 1, 0);
	used = vector<int> (n + 1, 0);
	vector<pair<int, int>> st1, st2;
	for (int i = 0; i < N; i++) {
		p[i] = i;
	}

	for (int i = 0; i < n; i++) {
		cin >> have[i].ft >> have[i].sc;
		was.pb(have[i].ft);
		was.pb(have[i].sc);
	}
	sort(was.begin(), was.end());
	sort(have.begin(), have.end());
	for (int i = 0; i < len(was); i++) 
		num[was[i]] = i;
	for (int i = 0; i < n; i++) {
		merge2(1, 0, N, num[have[i].ft], num[have[i].sc] + 1, i);
		add(N + num[have[i].sc], i);
	}

	int ans = 1;
	for (int i = 0; i < n; i++) {
		int pr = findp(i);
		if(!wasc[pr])
			ans = (ans * 2) % mod;
		wasc[pr] = 1;
	}
	for (int i = 0; i < n; i++) {
		if(used[i])
			continue;
		dfs(i, 1);
	}
	for (int i = 0; i < n; i++) {
		if(color[i] == 1) 
			st1.pb(have[i]);
		else
			st2.pb(have[i]);
	}
	if(!ch(st1) || !ch(st2)) {
		cout << 0;
		return 0;
	}
	cout << ans << endl;
	return 0;
}


/*
sort(check.begin(), check.end());
	vector<int> st1, st2;
	vector<int> from(n + 1, 0);
	for (auto x: check) {
		cout << x.ft << " " << x.sc << endl;
		if(x.sc >= 0) {
			bool can1 = 0, can2 = 0;
			if(len(st1) == 0 || st1.back() > have[x.sc].sc)
				can1 = 1;
			if(len(st2) == 0 || st2.back() > have[x.sc].sc) 
				can2 = 1;
			// cout << "C " << can1 << " " << can2 << endl;
			// if(len(st1) > 0) 
			// 	cout << "ST1 " << st1.back() << endl;
			// if(len(st2) > 0)
			// 	cout << "ST2 " << st2.back() << endl;
			if(!can1 && !can2) {
				cout << 0;
				return 0;
			}

			if(len(st1) == 0 && len(st2) == 0) {
				st1.pb(have[x.sc].sc);
				from[x.sc] = 1;
				continue;
			}

			if(len(st2) == 0 || st1.back() < st2.back()) {
				if(can1) {
					st1.pb(have[x.sc].sc);
					from[x.sc] = 1;
				}
				else {
					st2.pb(have[x.sc].sc);
					from[x.sc] = 2;
				}
			}
			else {
				if(can2) {
					st2.pb(have[x.sc].sc);
					from[x.sc] = 2;
				}
				else {
					st1.pb(have[x.sc].sc);
					from[x.sc] = 1;
				}
			}
		}
		else {
			x.sc = -x.sc - 1;
			if(from[x.sc] == 1)
				st1.pop_back();
			else
				st2.pop_back();
		}
	}
*/

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