Submission #31099

#	Time	Username	Problem	Language	Result	Execution time	Memory
31099		RezwanArefin01	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	17644 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e6 + 10;
int p[maxn * 2 + 100], n;
struct range{
	int l, r; 
	bool operator < (const range &p) const {
		return l == p.l ? r < p.r : l < p.l;
	}
} v[maxn];

bool cant(int i, int j) {
	return (v[i].l < v[j].l && v[j].l < v[i].r && v[j].r > v[i].r);
}

int find(int u) { return p[u] == u ? u : p[u] = find(p[u]); }
void construct() {
	sort(v, v+n);
	range q[n]; 
	for(int i = 0; i < n; i++) 
		q[i] = {v[i].l, i}; 
	for(int i = 0; i <= 2*n; i++) 
		p[i] = i;
	for(int i = 0; i < n; i++) {
		range xx = {v[i].r, 0}; 
		int x = lower_bound(v, v+n, v[i]) - v; 
		int y = upper_bound(v, v+n, xx) - v;
		for(int j = x; j <= y; j++) {
			if(cant(i, j) || cant(j, i)) {
				if(find(i) == find(j + n) || find(i + n) == find(j)) {
					cout <<"0\n"; exit(0);
				}
				p[find(i)] = find(j);
				p[find(j)] = find(i);

				p[find(j+n)] = find(j);
				p[find(i+n)] = find(i);
			}
		}	
	}
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	cin >> n; 
	for(int i = 0; i < n; i++) 
		cin >> v[i].l >> v[i].r; 

	construct(); 
	ll ret = 1;
	for(int i = 0; i < n; i++) 
		if(p[i] == i) {
			ret = ret * 2 % ll(1e9 + 7);
		}
	cout << ret << endl;
}

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