제출 #204988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204988		hanagasumi	Port Facility (JOI17_port_facility)	C++17	10 / 100	13 ms	1276 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;
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);
	// cout << "ADD " << v << " " << val << endl;
	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]) {
			// cout << "+ " << y << " " << val << endl;
			merge(x, y);
		}
		merge(x, val);
		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);
}


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> color(n, 0);
	vector<int> wasc(n + 1, 0);
	vector<int> used(n, 0);
	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++) {
		int now = 0;
		for (int j = 0; j < i; j++) {
			if(!(have[j].sc < have[i].sc)) 
				continue;
			if(have[j].sc < have[i].ft) 
				continue;
			if(have[i].ft <= used[j] && used[j] <= have[i].sc) {
				now = -1;
				break;
			}
			now = max(now, have[j].sc);
		}
		if(now == -1) {
			cout << 0;
			return 0;
		}
		used[i] = now;
	}


	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: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22