Submission #1255172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255172		g4yuhg	Port Facility (JOI17_port_facility)	C++20	22 / 100	1973 ms	1114112 KiB

port_facility

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll> 
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 2000006
#define endl '\n'
using namespace std;
 
bool ghuy4g;

const ll mod = 1e9 + 7;

void add(ll &u, ll v) {
	u += v;
	if (u >= mod) {
		u -= mod;
	}
}

ll n, d[N], idx[N];
pii a[N];

bool vst[N];

vector<ll> adj[N];

void dfs(ll u, ll parent) {
	vst[u] = 1;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		if (vst[v]) {
			if (d[v] == d[u]) {
				cout << 0;
				exit(0);
			}
			continue;
		}
		d[v] = 1 - d[u];
		dfs(v, u);
	}
}

void sub1() {
	for (int i = 1; i <= n; i ++) {
		for (int j = i + 1; j <= n; j ++) {
			if (i == j) continue;
			if (a[i].fi > a[j].se || a[j].fi > a[i].se) {
				continue;
			}
			if (a[i].fi < a[j].fi && a[j].se < a[i].se) continue;
			if (a[j].fi < a[i].fi && a[i].se < a[j].se) continue;
			adj[i].push_back(j);
			adj[j].push_back(i);
			//cout << i << " " << j << endl;
		}
	}
	ll tplt = 0, ans = 1;
	for (int i = 1; i <= n; i ++) {
		if (vst[i] == 0) {
			dfs(i, i);
			tplt ++ ;
			ans = ans * 2 % mod;
		}
	}
	//cout << "tplt " << tplt << endl;
	cout << ans << endl;
}

bool cmp(pii a, pii b) {
	return a.se < b.se;
}

void sub2() {
	sort(a + 1, a + 1 + n, cmp);
	set<ll> s;
	for (int i = 1; i <= n; i ++) {
		s.insert(a[i].fi);
		idx[a[i].fi] = i;
		//cout << i << " " << a[i].fi << " " << a[i].se << endl;
	} 
	for (int i = 1; i <= n; i ++) {
		s.erase(a[i].fi);
		auto it = s.lower_bound(a[i].fi);
		while (it != s.end()) {
			if (*it > a[i].se) break;
			//cout << i << " fi " << *it << endl;
			adj[i].push_back(idx[*it]);
			adj[idx[*it]].push_back(i);
			//cout << i << " " << idx[*it] << endl;
			it ++ ;
		}
	}
	ll tplt = 0, ans = 1;
	for (int i = 1; i <= n; i ++) {
		if (vst[i] == 0) {
			dfs(i, i);
			tplt ++ ;
			ans = ans * 2 % mod;
		}
	}
	//cout << "tplt " << tplt << endl;
	cout << ans << endl;
}

bool klinh;

signed main(void) {
	faster;
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].fi >> a[i].se;
	}
	
	sort(a + 1, a + 1 + n);
	
	sub2();
		
	cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
	return 0;
}

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