Submission #535447

#	Time	Username	Problem	Language	Result	Execution time	Memory
535447		iliaM	Port Facility (JOI17_port_facility)	C++17	100 / 100	3082 ms	233444 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = 2e6 + 10;

struct SegTree {
	int t[N << 2], zz;
	bool minmode;
	
	SegTree(bool mm) : minmode(mm) {
		zz = mm ? N : -1;
		fill(t, t + (N << 2), zz);
	}

	int pull(int l, int r) {
		if (minmode) {
			return min(l, r);
		}
		return max(l, r);
	}

	void update(int c, int b, int e, int i, int x) {
		if (e - b == 1) {
			t[c] = x;
			return;
		}
		int m = (b + e) >> 1, l = c << 1, r = l | 1;
		if (i < m) {
			update(l, b, m, i, x);
		} else {
			update(r, m, e, i, x);
		}
		t[c] = pull(t[l], t[r]);
	}

	int query(int c, int b, int e, int u, int v) {
		if (e <= u || v <= b) {
			return zz;
		}
		if (u <= b && e <= v) {
			return t[c];
		}
		int m = (b + e) >> 1, l = c << 1, r = l | 1;
		return pull(query(l, b, m, u, v), query(r, m, e, u, v));
	}
		
};

int n, ind[N], l[N], r[N];
bool isl[N];
SegTree segmn(true), segmx(false);
vector<int> vec[2];
bool color[N];
bool mark[N];

void dfs(int v) {
	mark[v] = true;
	segmn.update(1, 0, n << 1, r[v], segmn.zz);
	segmx.update(1, 0, n << 1, l[v], segmx.zz);
	vec[color[v]].push_back(l[v]);
	vec[color[v]].push_back(r[v]);

	int ret = segmn.query(1, 0, n << 1, l[v] + 1, r[v]);
	while (ret < l[v]) {
		color[ind[ret]] = color[v] ^ 1;
		dfs(ind[ret]);
		ret = segmn.query(1, 0, n << 1, l[v] + 1, r[v]);
	}
	ret = segmx.query(1, 0, n << 1, l[v] + 1, r[v]);
	while (ret > r[v]) {
		color[ind[ret]] = color[v] ^ 1;
		dfs(ind[ret]);
		ret = segmx.query(1, 0, n << 1, l[v] + 1, r[v]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
		
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> l[i] >> r[i];
		--l[i], --r[i];
		ind[l[i]] = ind[r[i]] = i;
		isl[l[i]] = true;
		segmn.update(1, 0, n << 1, r[i], l[i]);
		segmx.update(1, 0, n << 1, l[i], r[i]);
	}
	
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (!mark[i]) {
			++cnt;
			for (int j = 0; j < 2; ++j) {
				vec[j].clear();
			}
			dfs(i);

			for (int j = 0; j < 2; ++j) {
				sort(vec[j].begin(), vec[j].end());
				vector<int> stk;
				for (auto &x : vec[j]) {
					if (isl[x]) {
						stk.push_back(x);
					} else {
						if (stk.back() != l[ind[x]]) {
							cout << 0;
							exit(0);
						}
						stk.pop_back();
					}
				}
			}
		}
	}

	int res = 1;
	while (cnt--) {
		res <<= 1;
		if (res >= 1000000007) {
			res -= 1000000007;
		}
	}

	cout << res;
}

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