Submission #205020

#	Time	Username	Problem	Language	Result	Execution time	Memory
205020		hanagasumi	Port Facility (JOI17_port_facility)	C++17	78 / 100	6102 ms	731420 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>
// #include <bits/stdc++.h>
 

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll
 

// #define FAST_ALLOCATOR_MEMORY (2e9)

// #ifdef FAST_ALLOCATOR_MEMORY
// 	int allocator_pos = 0;
// 	char allocator_memory[(int)FAST_ALLOCATOR_MEMORY];
// 	inline void * operator new ( size_t n ) {
// 		char *res = allocator_memory + allocator_pos;
// 		allocator_pos += n;
// 		assert(allocator_pos <= (int)FAST_ALLOCATOR_MEMORY);
// 		return (void *)res;
// 	}
// 	inline void operator delete ( void * ) noexcept { }
// #endif

using namespace std;
typedef long long ll;
typedef long double ld;


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


const int N = 1 << 21;
vector<int> tree[2 * N];
vector<int> g[N];
int p[N];
int sz[N];
int color[N];
int used[N];

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;
}

bool one(int a, int b) {
	a = findp(a), b = findp(b);
	if(a == b)
		return 0;
	return 1;
}

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);
		}
		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);
	for (int i = 0; i < N; i++) {
		p[i] = i;
		sz[i] = 1;
		color[i] = 0;
		used[i] = 0;
	}
	vector<int> was;
	map<int, int> num;
	vector<pair<int, int>> have(n);
	vector<int> wasc(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 cnt = 0;
	for (int i = 0; i < n; i++) {
		if(used[i])
			continue;
		dfs(i, 1);
		cnt++;
	}

	ll ans = 1;
	for (int i = 0; i < cnt; i++) {
		ans = (ans * 2LL) % mod;
	}
	
	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