Submission #46583

# Submission time Handle Problem Language Result Execution time Memory
46583 2018-04-21T14:49:14 Z maksim_gaponov Port Facility (JOI17_port_facility) C++14
0 / 100
31 ms 33560 KB
#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 mem_size = 0;
char mem[20 * MAXN];

inline void* operator new (size_t n) {
    char *res = mem + mem_size;
    mem_size += n;
    return res;
}

inline void operator delete (void*) noexcept { }

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 get_max_end(int i, int j) {
	if (i == -1)
		return j;
	if (j == -1)
		return i;
	if (segment_end[i] > segment_end[j])
		return i;
	return j;
}

int get_min_start(int i, int j) {
	if (i == -1)
		return j;
	if (j == -1)
		return i;
	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 -1;
	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 -1;
	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);
	int n;
	cin >> n;
	memset(max_end, 255, sizeof(max_end));
	memset(min_start, 255, sizeof(min_start));
	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 * n, segment_end[i], i);
		update_ends(0, 0, 2 * n, 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 * n, segment_start[cur], -1);
			update_starts(0, 0, 2 * n, segment_end[cur], -1);
			while (true) {
				int f = query_ends(0, 0, 2 * n, segment_start[cur], segment_end[cur] + 1);
				if (f == -1 || segment_end[f] < segment_end[cur])
					break;
				update_ends(0, 0, 2 * n, segment_start[f], -1);
				color[f] = -color[cur];
				q.push(f);
			}
			while (true) {
				int f = query_starts(0, 0, 2 * n, segment_start[cur], segment_end[cur] + 1);
				if (f == -1 || segment_start[f] > segment_start[cur])
					break;
				update_starts(0, 0, 2 * n, segment_end[f], -1);
				color[f] = -color[cur];
				q.push(f);
			}
		}
	}
	for (int i = 0; i < 2 * n; i++) {
		int id = actions[i];
		int type = !active[i];
		if (type == true) {
            type = active[i] = 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;
}
# Verdict Execution time Memory Grader output
1 Correct 30 ms 33272 KB Output is correct
2 Correct 31 ms 33412 KB Output is correct
3 Correct 27 ms 33440 KB Output is correct
4 Correct 27 ms 33460 KB Output is correct
5 Correct 28 ms 33460 KB Output is correct
6 Correct 27 ms 33460 KB Output is correct
7 Correct 25 ms 33460 KB Output is correct
8 Correct 28 ms 33460 KB Output is correct
9 Correct 27 ms 33460 KB Output is correct
10 Correct 27 ms 33460 KB Output is correct
11 Incorrect 27 ms 33560 KB Output isn't correct
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 30 ms 33272 KB Output is correct
2 Correct 31 ms 33412 KB Output is correct
3 Correct 27 ms 33440 KB Output is correct
4 Correct 27 ms 33460 KB Output is correct
5 Correct 28 ms 33460 KB Output is correct
6 Correct 27 ms 33460 KB Output is correct
7 Correct 25 ms 33460 KB Output is correct
8 Correct 28 ms 33460 KB Output is correct
9 Correct 27 ms 33460 KB Output is correct
10 Correct 27 ms 33460 KB Output is correct
11 Incorrect 27 ms 33560 KB Output isn't correct
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 30 ms 33272 KB Output is correct
2 Correct 31 ms 33412 KB Output is correct
3 Correct 27 ms 33440 KB Output is correct
4 Correct 27 ms 33460 KB Output is correct
5 Correct 28 ms 33460 KB Output is correct
6 Correct 27 ms 33460 KB Output is correct
7 Correct 25 ms 33460 KB Output is correct
8 Correct 28 ms 33460 KB Output is correct
9 Correct 27 ms 33460 KB Output is correct
10 Correct 27 ms 33460 KB Output is correct
11 Incorrect 27 ms 33560 KB Output isn't correct
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 30 ms 33272 KB Output is correct
2 Correct 31 ms 33412 KB Output is correct
3 Correct 27 ms 33440 KB Output is correct
4 Correct 27 ms 33460 KB Output is correct
5 Correct 28 ms 33460 KB Output is correct
6 Correct 27 ms 33460 KB Output is correct
7 Correct 25 ms 33460 KB Output is correct
8 Correct 28 ms 33460 KB Output is correct
9 Correct 27 ms 33460 KB Output is correct
10 Correct 27 ms 33460 KB Output is correct
11 Incorrect 27 ms 33560 KB Output isn't correct
12 Halted 0 ms 0 KB -