Submission #982581

#	Time	Username	Problem	Language	Result	Execution time	Memory
982581		AmirAli_H1	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	424 KiB

port_facility

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

int n;
const int maxn = 4000 + 4;
const int mod = 1e9 + 7;
pii A[maxn]; int ind[maxn];
int val[maxn]; set<pii> st;
int p[maxn], num;

int get(int a) {
	return (p[a] == a) ? a : p[a] = get(p[a]);
}

void merge(int a, int b) {
	a = get(a); b = get(b);
	if (a == b) return ;
	p[a] = b; num--;
}

ll power(ll a, ll b) {
	if (b == 0) return 1;
	return power(a * a % mod, b / 2) * ((b & 1) ? a : 1) % mod;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i].F >> A[i].S;
		A[i].F--; A[i].S--;
		ind[A[i].F] = i; ind[A[i].S] = i;
	}
	
	for (int j = 2 * n - 1; j >= 0; j--) {
		int i = ind[j];
		if (A[i].S == j) {
			auto it = st.upper_bound(Mp(A[i].F, 2 * n));
			if (it != st.end()) {
				auto f = *it;
				if (f.F < A[i].S) val[i] = f.S;
				else val[i] = -1;
			}
			st.insert(Mp(A[i].F, i));
		}
	}
	
	for (int i = 0; i < n; i++) {
		if (val[i] == -1 || val[val[i]] == -1) continue;
		int j = val[val[i]];
		if (A[j].F > A[i].F && A[j].F < A[i].S && A[j].S > A[i].S) {
			kill(0);
		}
	}
	
	iota(p, p + n, 0); num = n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (A[j].F > A[i].F && A[j].F < A[i].S && A[j].S > A[i].S) {
				merge(i, j);
			}
		}
	}
	
	cout << power(2, num) << endl;
	
	return 0;
}

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