Submission #771406

#	Time	Username	Problem	Language	Result	Execution time	Memory
771406		NK_	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	212 KiB

port_facility

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair

using ll = long long;
using pi = pair<int, int>;
template<class T> using V = vector<T>;
using vi = V<int>;

struct DSU {
	vi e; void init(int N) { e = vi(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool unite(int x, int y) {
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	V<pi> E(2*N);

	vi A(N), B(N); for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i]; --A[i], --B[i];
		E[A[i]] = mp(i, +1);
		E[B[i]] = mp(i, -1);
	}

	DSU D; D.init(N); 
	set<pi> R; int P = N;
	for(int t = 0; t < 2 * N; t++) {
		int i = E[t].f;
		// cout << t << " -> " << i << endl;
		if (E[t].s == +1) {
			for(auto r : R) {
				if (r.f > B[i]) break;
				if (!D.unite(i, r.s)) {
					cout << 0 << nl;
					exit(0);
				} else P--;
			}

			R.insert(mp(B[i], i));
		}

		if (E[t].s == -1) {
			R.erase(mp(B[i], i));
		}
	}


	const int MOD = 1e9 + 7;
	ll ANS = 1, x = 2;

	for(; P; P /= 2, x = (x * x) % MOD) if (P & 1) ANS = (ANS * x) % MOD;

	cout << ANS << nl;







    return 0;
}

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