Submission #984335

#	Time	Username	Problem	Language	Result	Execution time	Memory
984335		yellowtoad	Port Facility (JOI17_port_facility)	C++17	10 / 100	28 ms	50076 KiB

port_facility

#include <iostream>
#include <algorithm>
#include <vector>
#define f first
#define s second
#define int long long
using namespace std;

const int mod = 1e9+7;
int n, d[2000010], p[2000010], cnt, ans = 1;
bool hv;
pair<int,int> a[1000010];
vector<int> aa, bb, amin, bmin, v[2000010], tmp;

bool check(int i, int j) {
	if ((a[i].f < a[j].f) && (a[j].f < a[i].s) && (a[i].s < a[j].s)) return 1;
	swap(i,j);
	if ((a[i].f < a[j].f) && (a[j].f < a[i].s) && (a[i].s < a[j].s)) return 1;
	return 0;
}

int dsu(int u) {
	if (p[u] == u) return u;
	return p[u] = dsu(p[u]);
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i].f >> a[i].s;
	sort(a+1,a+n+1);
	for (int i = 1; i <= n; i++) p[i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			if (check(i,j)) p[dsu(i)] = p[dsu(j)];
		}
	}
	for (int i = 1; i <= n; i++) {
		hv = 0;
		aa.clear(); amin.clear();
		for (int j = 1; j <= n; j++) {
			if (p[dsu(j)] == i) {
				while (aa.size() && (aa.back() < a[j].f)) {
					aa.pop_back();
					while (amin.size() && ((aa.empty()) || (amin.back() < aa.back()))) {
						tmp.push_back(amin.back());
						amin.pop_back();
					}
					while (tmp.size()) {
						aa.push_back(tmp.back());
						tmp.pop_back();
					}
				}
				if ((aa.empty()) || (aa.back() > a[j].s)) {
					aa.push_back(a[j].s);
				} else {
					if (amin.size() && (amin.back() < a[j].s)) {
						cout << 0 << endl;
						return 0;
					}
					amin.push_back(a[j].s);
				}
				hv = 1;
			}
		}
		cnt += hv;
	}
	for (int i = 1; i <= cnt; i++) (ans *= 2) %= mod;
	cout << ans << endl;
}

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