Submission #41229

#	Time	Username	Problem	Language	Result	Execution time	Memory
41229		ssnsarang2023	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	376 KiB

port_facility

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

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[N], hi[N];
ii tree[3][1 << 21], a[N];

void merge_tree(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(ii tr[], int k, int l, int r) {
	if (l > r) return;
	if (l == r) {
		tr[k].first = a[l].second, tr[k].second = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(tr, k << 1, l, mid);
	build(tr, k << 1 | 1, mid + 1, r);
	merge_tree(tr, k, k << 1, k << 1 | 1);
}

void update(ii tr[], int k, int l, int r, int pos, const ii &val) {
	if (l > r || l > pos || r < pos) return;
	if (l == r && l == pos) {
		tr[k] = val;
		return;
	}
	int mid = (l + r) >> 1;
	update(tr, k << 1, l, mid, pos, val);
	update(tr, k << 1 | 1, mid + 1, r, pos, val);
	merge_tree(tr, k, k << 1, k << 1 | 1);
}

ii query(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(tr, k << 1, l, mid, L, R);
	ii rt = query(tr, k << 1 | 1, mid + 1, r, L, R);
	if (lf.first < rt.first) return rt;
	return lf;
}

bool check(int idx, int id) {
	ii tmp = query(tree[id], 1, 1, n, lo[idx], hi[idx]);
	return tmp.first <= a[idx].second;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].first, &a[i].second);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		lo[i] = i;
		hi[i] = upper_bound(a + i, a + n + 1, ii(a[i].second, 0)) - a - 1;
	}
	build(tree[0], 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;
		update(tree[0], 1, 1, n, i, ii(0, 0));
		while (SZ(q)) {
			int u = q.front(); q.pop();
			update(tree[vis[u]], 1, 1, n, u, ii(a[u].second, u));
			if (!check(u, vis[u])) return printf("0"), 0;
			ii tmp = query(tree[0], 1, 1, n, lo[u], hi[u]);
			while (tmp.first > a[u].second) {
				vis[tmp.second] = 3 - vis[u];
				q.push(tmp.second);
				update(tree[0], 1, 1, n, tmp.second, ii(0, 0));
				tmp = query(tree[0], 1, 1, n, lo[u], hi[u]);
			}
		}
		ans = ans * 2 % base;
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:66:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
port_facility.cpp:67:71: 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[i].first, &a[i].second);
                                                                       ^

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