Submission #47117

#	Time	Username	Problem	Language	Result	Execution time	Memory
47117		maksim_gaponov	Port Facility (JOI17_port_facility)	C++14	100 / 100	4851 ms	261384 KiB

port_facility

#ifdef KEK
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
const int mod = 1000000007;

void openFiles() {
#ifdef KEK
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

const int MAXN = 1048576;

int max_end[2 * 2 * MAXN];
int min_start[2 * 2 * MAXN];
int color[MAXN];
int segment_start[MAXN], segment_end[MAXN];
bool used[MAXN];
bool active[MAXN];

int actions[2 * MAXN];
queue<int> q;
int n;

int get_max_end(int i, int j) {
	if (segment_end[i] > segment_end[j])
		return i;
	return j;
}

int get_min_start(int i, int j) {
	if (segment_start[i] < segment_start[j])
		return i;
	return j;
}

void update_ends(int x, int l, int r, int i, int val) {
	if (l > i || r <= i)
		return;
	if (r - l == 1) {
		max_end[x] = val;
		return;
	}
	int c = (l + r) / 2;
	update_ends(2 * x + 1, l, c, i, val);
	update_ends(2 * x + 2, c, r, i, val);
	max_end[x] = get_max_end(max_end[2 * x + 1], max_end[2 * x + 2]);
}

void update_starts(int x, int l, int r, int i, int val) {
	if (l > i || r <= i)
		return;
	if (r - l == 1) {
		min_start[x] = val;
		return;
	}
	int c = (l + r) / 2;
	update_starts(2 * x + 1, l, c, i, val);
	update_starts(2 * x + 2, c, r, i, val);
	min_start[x] = get_min_start(min_start[2 * x + 1], min_start[2 * x + 2]);
}

int query_ends(int x, int l, int r, int ql, int qr) {
	if (l >= qr || r <= ql)
		return n;
	if (ql <= l && r <= qr)
		return max_end[x];
	int c = (l + r) / 2;
	return get_max_end(
		query_ends(2 * x + 1, l, c, ql, qr),
		query_ends(2 * x + 2, c, r, ql, qr)
	);
}

int query_starts(int x, int l, int r, int ql, int qr) {
	if (l >= qr || r <= ql)
		return n;
	if (ql <= l && r <= qr)
		return min_start[x];
	int c = (l + r) / 2;
	return get_min_start(
		query_starts(2 * x + 1, l, c, ql, qr),
		query_starts(2 * x + 2, c, r, ql, qr)
	);
}

vector<int> v[2];

int main() {
	openFiles();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	fill(max_end, max_end + 4 * MAXN, n);
	fill(min_start, min_start + 4 * MAXN, n);
	segment_start[n] = 2 * MAXN;
	segment_end[n] = -1;
	for (int i = 0; i < n; i++) {
        cin >> segment_start[i] >> segment_end[i];
		segment_start[i]--;
		segment_end[i]--;
		update_starts(0, 0, 2 * MAXN, segment_end[i], i);
		update_ends(0, 0, 2 * MAXN, segment_start[i], i);
		actions[segment_start[i]] = i;
		actions[segment_end[i]] = i;
	}
	int ans = 1;
	int itr = 0;
	while (true) {
		while (itr != n && used[itr])
			itr++;
		if (itr == n)
			break;
		ans *= 2;
		if (ans >= mod)
            ans -= mod;
		q.push(itr);
		color[itr] = 1;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			used[cur] = true;
			update_ends(0, 0, 2 * MAXN, segment_start[cur], n);
			update_starts(0, 0, 2 * MAXN, segment_end[cur], n);
			while (true) {
				int f = query_ends(0, 0, 2 * MAXN, segment_start[cur], segment_end[cur] + 1);
				if (f == n || segment_end[f] < segment_end[cur])
					break;
				update_ends(0, 0, 2 * MAXN, segment_start[f], n);
                if (color[cur] == color[f]) {
                    cout << "0";
                    return 0;
                }
				color[f] = -color[cur];
				q.push(f);
			}
			while (true) {
				int f = query_starts(0, 0, 2 * MAXN, segment_start[cur], segment_end[cur] + 1);
				if (f == n || segment_start[f] > segment_start[cur])
					break;
				update_starts(0, 0, 2 * MAXN, segment_end[f], n);
                if (color[cur] == color[f]) {
                    cout << "0";
                    return 0;
                }
				color[f] = -color[cur];
				q.push(f);
			}
		}
	}
	for (int i = 0; i < 2 * n; i++) {
		int id = actions[i];
		int type = !active[id];
		if (type == true) {
            type = active[id] = true;
		}
		if (type) {
			v[(color[id] + 1) / 2].push_back(id);
		}
		else {
			if (v[(color[id] + 1) / 2].back() != id) {
				cout << "0";
				return 0;
			}
			v[(color[id] + 1) / 2].pop_back();
		}
	}
	cout << ans;
	return 0;
}

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