Submission #41230

#	Time	Username	Problem	Language	Result	Execution time	Memory
41230		ssnsarang2023	Port Facility (JOI17_port_facility)	C++14	100 / 100	4211 ms	647636 KiB

port_facility

#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <cstring>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;

#define SZ(x) ((int)x.size())

const int N = (int)1e6+5;
const int base = (int)1e9+7;
int n, vis[N], lo[2][N], hi[2][N], b[2][N];
ii tree[2][1 << 21], a[2][N];

void merge_tree_min(ii tr[], int root, int lf, int rt) {
	if (tr[lf].first > tr[rt].first)
		tr[root] = tr[rt];
	else tr[root] = tr[lf];
}

void merge_tree_max(ii tr[], int root, int lf, int rt) {
	if (tr[lf].first < tr[rt].first)
		tr[root] = tr[rt];
	else tr[root] = tr[lf];
}

void build(int k, int l, int r) {
	if (l > r) return;
	if (l == r) {
		tree[0][k] = ii(a[0][l].second, l);
		tree[1][k] = ii(a[1][l].second, l);
		return;
	}
	int mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	merge_tree_max(tree[0], k, k << 1, k << 1 | 1);
	merge_tree_min(tree[1], k, k << 1, k << 1 | 1);
}

void _remove_max(int k, int l, int r, int pos) {
	if (l > r || l > pos || r < pos) return;
	if (l == r && l == pos) {
		tree[0][k] = ii(0, 0);
		return;
	}
	int mid = (l + r) >> 1;
	_remove_max(k << 1, l, mid, pos);
	_remove_max(k << 1 | 1, mid + 1, r, pos);
	merge_tree_max(tree[0], k, k << 1, k << 1 | 1);
}

void _remove_min(int k, int l, int r, int pos) {
	if (l > r || l > pos || r < pos) return;
	if (l == r && l == pos) {
		tree[1][k] = ii(2*n+1, 0);
		return;
	}
	int mid = (l + r) >> 1;
	_remove_min(k << 1, l, mid, pos);
	_remove_min(k << 1 | 1, mid + 1, r, pos);
	merge_tree_min(tree[1], k, k << 1, k << 1 | 1);
}

ii query_max(ii tr[], int k, int l, int r, int L, int R) {
	if (l > r || l > R || r < L) return ii(0, 0);
	if (L <= l && r <= R) return tr[k];
	int mid = (l + r) >> 1;
	ii lf = query_max(tr, k << 1, l, mid, L, R);
	ii rt = query_max(tr, k << 1 | 1, mid + 1, r, L, R);
	if (lf.first < rt.first) return rt;
	return lf;
}

ii query_min(ii tr[], int k, int l, int r, int L, int R) {
	if (l > r || l > R || r < L) return ii(2*n+1, 0);
	if (L <= l && r <= R) return tr[k];
	int mid = (l + r) >> 1;
	ii lf = query_min(tr, k << 1, l, mid, L, R);
	ii rt = query_min(tr, k << 1 | 1, mid + 1, r, L, R);
	if (lf.first > rt.first) return rt;
	return lf;
}

int bit[2*N];

void update_bit(int idx, int val) {
	for (; idx <= 2*n; idx += idx & -idx)
		bit[idx] += val;
}

int read_bit(int idx) {
	int ans = 0;
	for (; idx > 0; idx -= idx & -idx)
		ans += bit[idx];
	return ans;
}

bool check(int id) {
	memset(bit, 0, sizeof(bit));
	vector<ii> c;
	for (int i = 1; i <= n; ++i) if (vis[i] == id)
		c.push_back(a[0][i]);
	for (int i = 0; i < SZ(c); ++i) {
		int tmp = read_bit(c[i].second) - read_bit(c[i].first);
		if (tmp > 0) return false;
		update_bit(c[i].second, 1);
	}
	return true;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &a[0][i].first, &a[0][i].second), a[1][i] = a[0][i];
	sort(a[0] + 1, a[0] + n + 1);
	for (int i = 1; i <= n; ++i) {
		lo[0][i] = i;
		hi[0][i] = upper_bound(a[0] + i, a[0] + n + 1, ii(a[0][i].second, 0)) - a[0] - 1;
		swap(a[1][i].first, a[1][i].second);
	}
	sort(a[1] + 1, a[1] + n + 1);
	for (int i = 1; i <= n; ++i) {
		hi[1][i] = i;
		lo[1][i] = lower_bound(a[1] + 1, a[1] + i, ii(a[1][i].second, 0)) - a[1];
		b[1][i] = lower_bound(a[0] + 1, a[0] + n + 1, ii(a[1][i].second, 0)) - a[0];
		b[0][i] = lower_bound(a[1] + 1, a[1] + n + 1, ii(a[0][i].second, 0)) - a[1];
	}
	build(1, 1, n);
	int ans = 1;
	for (int i = 1; i <= n; ++i) if (!vis[i]) {
		queue<int> q;
		q.push(i);
		vis[i] = 1;
		_remove_max(1, 1, n, i);
		_remove_min(1, 1, n, b[0][i]);
		while (SZ(q)) {
			int u = q.front(); q.pop();
			ii tmp = query_max(tree[0], 1, 1, n, lo[0][u], hi[0][u]);
			while (tmp.first > a[0][u].second) {
				vis[tmp.second] = 3 - vis[u];
				q.push(tmp.second);
				_remove_max(1, 1, n, tmp.second);
				_remove_min(1, 1, n, b[0][tmp.second]);
				tmp = query_max(tree[0], 1, 1, n, lo[0][u], hi[0][u]);
			}
			int u2 = b[0][u];
			tmp = query_min(tree[1], 1, 1, n, lo[1][u2], hi[1][u2]);
			while (tmp.first < a[1][u2].second) {
				vis[b[1][tmp.second]] = 3 - vis[u];
				q.push(b[1][tmp.second]);
				_remove_min(1, 1, n, tmp.second);
				_remove_max(1, 1, n, b[1][tmp.second]);
				tmp = query_min(tree[1], 1, 1, n, lo[1][u2], hi[1][u2]);
			}
		}
		ans = ans * 2 % base;
	}
	if (check(1) && check(2)) printf("%d", ans);
	else printf("0");
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:119:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
port_facility.cpp:120:96: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; ++i) scanf("%d%d", &a[0][i].first, &a[0][i].second), a[1][i] = a[0][i];
                                                                                                ^

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