Submission #36944

#	Time	Username	Problem	Language	Result	Execution time	Memory
36944		cheater2k	Port Facility (JOI17_port_facility)	C++14	78 / 100	2216 ms	886516 KiB

port_facility

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

const int N = 1e6 + 5; // TODO: fix

struct Node {
	int L; int R; int cnt;
	Node() { L = R = cnt = 0; }
} T[N * 20];

int pos[N * 2][2], segl[N * 2], segr[N * 2];
vector< pair<int,int> > G[N * 20];
bool color[N * 20]; int cnt; // for bipartite checking
bool vis[N * 20]; // for BFS
int n, peak, version;
pair<int,int> a[N];
vector<int> z;

#define mid ((l + r) >> 1)
int build(int l, int r) {
	if (l == r) {
		pos[l][1] = ++peak; // on
		T[peak].L = T[peak].R = peak; T[peak].cnt = 1;
		pos[l][0] = ++peak; // off
		T[peak].L = T[peak].R = peak;
		return peak; // currently off
	}
	int le = build(l, mid), ri = build(mid + 1, r);
	++peak; T[peak].L = le; T[peak].R = ri;
	return peak;
}

int upd(int v, int l, int r, int p, int val) {
	if (l > r || l > p || r < p) return v;
	if (l == r) return pos[p][val];
	int le = upd(T[v].L, l, mid, p, val);
	int ri = upd(T[v].R, mid + 1, r, p, val);
	++peak; T[peak].L = le; T[peak].R = ri;
	T[peak].cnt = T[T[peak].L].cnt + T[T[peak].R].cnt;
	//printf("new node: %d -> L = %d R = %d\n", peak, T[peak].L, T[peak].R);
	return peak;
}

void add(int cur, int v, int l, int r, int L, int R) {
	if (l > r || R < l || L > r) return;
	if (L <= l && r <= R) {
		// cur and v belong to different sides in the bipartite graph
		if (!T[v].cnt) return; // off
		G[cur].push_back(make_pair(1, v)); G[v].push_back(make_pair(1, cur));
		vis[v] = true;
		return;
	}
	add(cur, T[v].L, l, mid, L, R); add(cur, T[v].R, mid + 1, r, L, R);
}
#undef mid

void dfs(int u) {
	vis[u] = 1;
	for (auto e : G[u]) {
		int v = e.second, id = e.first;
		if (!vis[v]) {
			color[v] = (color[u] ^ id); dfs(v);
		} else if (vis[v] && color[v] != (color[u] ^ id)) {
			printf("0\n"); exit(0); // invalid
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		segl[a[i].first] = i;
		segr[a[i].second] = i;
		z.push_back(a[i].second);
	}
	sort(z.begin(), z.end());
	z.erase(unique(z.begin(), z.end()), z.end());
	version = build(1, n);

	for (int lef = 1; lef <= 2 * n; ++lef) {
		int del = segr[lef - 1];
		int plef = lower_bound(z.begin(), z.end(), lef) - z.begin() + 1;
		if (del) {
			// delete
			version = upd(version, 1, n, plef - 1, 0);
		}
		int cur = segl[lef];
		if (!cur) continue;
		int rig = a[cur].second;
		int prig = lower_bound(z.begin(), z.end(), rig) - z.begin() + 1;

		// add
		add(pos[prig][1], version, 1, n, plef, prig);
		// update
		version = upd(version, 1, n, prig, 1);
	}

	// BFS
	queue <int> qu;
	for (int i = 1; i <= peak; ++i) if (vis[i]) qu.push(i);
	while(!qu.empty()) {
		int u = qu.front(); qu.pop();
		if (T[T[u].L].cnt) {
			G[u].push_back(make_pair(0, T[u].L)); G[T[u].L].push_back(make_pair(0, u));
			if (!vis[T[u].L]) {
				qu.push(T[u].L);
				vis[T[u].L] = true;
			}
		}
		if (T[T[u].R].cnt) {
			G[u].push_back(make_pair(0, T[u].R)); G[T[u].R].push_back(make_pair(0, u));
			if (!vis[T[u].R]) {
				qu.push(T[u].R);
				vis[T[u].R] = true;
			}
		}
	}

	// check for bipartite graph
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= z.size(); ++i) {
		if (!vis[pos[i][1]]) {
			++cnt; color[pos[i][1]] = 0; dfs(pos[i][1]);
		}
	}
	int ans = 1;
	while(cnt-- > 0) ans = 2LL * ans % (int)(1e9 + 7);
	printf("%d\n", ans);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= z.size(); ++i) {
                    ^

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