Submission #850484

#	Time	Username	Problem	Language	Result	Execution time	Memory
850484		mickey080929	Port Facility (JOI17_port_facility)	C++17	100 / 100	930 ms	65360 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int mod = 1e9 + 7;

struct DisjointSet{
	int n;
	vector<int> par;
	void Init(int _n) {
		n = _n;
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int Find(int x) {
		if (par[x] == x) return x;
		return par[x] = Find(par[x]);
	}
	void Union(int x, int y) {
		x = Find(x);
		y = Find(y);
		if (x == y) return;
		par[y] = x;
	}
} dsu;

struct SegmentTree{
public:
	int n;
	vector<int> tree;
	void Init(int _n) {
		n = _n;
		int sz = 1<<(Log2(n)+1);
		tree.resize(sz);
		fill(tree.begin(), tree.end(), -1);
	}
	void Update(int tar, int val) { Update(1, 1, n, tar, val); }
	int Query(int l, int r) { return Query(1, 1, n, l, r); }
private:
	static int Log2(int n) {
		int ret = 0;
		while (n > 1 << ret) ret ++;
		return ret;
	}
	void Update(int node, int s, int e, int tar, int val) {
		if (s > tar || tar > e) return;
		if (s == e) {
			tree[node] = val;
			return;
		}
		int mid = s + e >> 1;
		Update(node<<1, s, mid, tar, val);
		Update(node<<1|1, mid+1, e, tar, val);
		tree[node] = max(tree[node<<1], tree[node<<1|1]);
	}
	int Query(int node, int s, int e, int l, int r) {
		if (l > e || s > r) return -1;
		if (l <= s && e <= r) return tree[node];
		int mid = s + e >> 1;
		return max(Query(node<<1, s, mid, l, r), Query(node<<1|1, mid+1, e, l, r));
	}
} seg;

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin >> n;
	vector<pii> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end());
	seg.Init(2*n);
	dsu.Init(2*n);
	vector<int> chk(2*n, 0), nxt(2*n+1, -1);
	for (int i=0; i<n; i++) {
		if (i) {
			for (int j=a[i-1].first+1; j<=a[i].first-1; j++) {
				if (nxt[j] == -1) continue;
				seg.Update(j, -1);
				seg.Update(a[nxt[j]].second, nxt[j]);
			}
		}
		vector<int> v;
		while (true) {
			int ret = seg.Query(a[i].first, a[i].second);
			if (ret == -1) break;
			v.push_back(ret);
			seg.Update(a[ret].second, -1);
		}
		if (!v.empty()) {
			sort(v.begin(), v.end(), [&] (int &u, int &v) { return a[u].first > a[v].first; });
			for (auto &x : v) {
				chk[dsu.Find(x<<1)] = 1;
				if (chk[dsu.Find(x<<1)^1]) {
					cout << "0\n";
					return 0;
				}
			}
			for (auto &x : v) chk[dsu.Find(x<<1)] = 0;
			for (auto &x : v) {
				dsu.Union(v[0]<<1, x<<1);
				dsu.Union(v[0]<<1^1, x<<1^1);
			}
			dsu.Union(v[0]<<1^1, i<<1);
			dsu.Union(v[0]<<1, i<<1^1);
			for (int j=0; j<(int)v.size()-1; j++) {
				nxt[a[v[j]].second] = v[j+1];
			}
			seg.Update(a[v[0]].second, v[0]);
		}
		seg.Update(a[i].second, i);
	}
	int ans = 1;
	for (int i=0; i<n; i++) {
		assert((dsu.Find(i<<1)^1) == dsu.Find(i<<1^1));
		if (dsu.Find(i<<1) == (i<<1)) {
			ans = ans * 2 % mod;
		}
	}
	cout << ans << '\n';
}

Compilation message (stderr)

port_facility.cpp: In member function 'void SegmentTree::Update(int, int, int, int, int)':
port_facility.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = s + e >> 1;
      |             ~~^~~
port_facility.cpp: In member function 'int SegmentTree::Query(int, int, int, int, int)':
port_facility.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid = s + e >> 1;
      |             ~~^~~

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