oj.uz

Submission #47117

# Submission time Handle Problem Language Result Execution time Memory
47117 2018-04-27T16:59:06 Z maksim_gaponov Port Facility (JOI17_port_facility) C++14
100 / 100
 4851 ms 261384 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 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33144 KB Output is correct
2 Correct 27 ms 33252 KB Output is correct
3 Correct 33 ms 33328 KB Output is correct
4 Correct 28 ms 33344 KB Output is correct
5 Correct 26 ms 33380 KB Output is correct
6 Correct 27 ms 33380 KB Output is correct
7 Correct 26 ms 33380 KB Output is correct
8 Correct 26 ms 33380 KB Output is correct
9 Correct 27 ms 33456 KB Output is correct
10 Correct 27 ms 33456 KB Output is correct
11 Correct 26 ms 33456 KB Output is correct
12 Correct 27 ms 33456 KB Output is correct
13 Correct 28 ms 33456 KB Output is correct
14 Correct 25 ms 33456 KB Output is correct
15 Correct 28 ms 33456 KB Output is correct
16 Correct 26 ms 33456 KB Output is correct
17 Correct 26 ms 33456 KB Output is correct
18 Correct 26 ms 33516 KB Output is correct
19 Correct 27 ms 33516 KB Output is correct
20 Correct 30 ms 33548 KB Output is correct
21 Correct 26 ms 33548 KB Output is correct
22 Correct 26 ms 33548 KB Output is correct
23 Correct 29 ms 33548 KB Output is correct
24 Correct 26 ms 33548 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33144 KB Output is correct
2 Correct 27 ms 33252 KB Output is correct
3 Correct 33 ms 33328 KB Output is correct
4 Correct 28 ms 33344 KB Output is correct
5 Correct 26 ms 33380 KB Output is correct
6 Correct 27 ms 33380 KB Output is correct
7 Correct 26 ms 33380 KB Output is correct
8 Correct 26 ms 33380 KB Output is correct
9 Correct 27 ms 33456 KB Output is correct
10 Correct 27 ms 33456 KB Output is correct
11 Correct 26 ms 33456 KB Output is correct
12 Correct 27 ms 33456 KB Output is correct
13 Correct 28 ms 33456 KB Output is correct
14 Correct 25 ms 33456 KB Output is correct
15 Correct 28 ms 33456 KB Output is correct
16 Correct 26 ms 33456 KB Output is correct
17 Correct 26 ms 33456 KB Output is correct
18 Correct 26 ms 33516 KB Output is correct
19 Correct 27 ms 33516 KB Output is correct
20 Correct 30 ms 33548 KB Output is correct
21 Correct 26 ms 33548 KB Output is correct
22 Correct 26 ms 33548 KB Output is correct
23 Correct 29 ms 33548 KB Output is correct
24 Correct 26 ms 33548 KB Output is correct
25 Correct 40 ms 33548 KB Output is correct
26 Correct 30 ms 33548 KB Output is correct
27 Correct 33 ms 33548 KB Output is correct
28 Correct 34 ms 33548 KB Output is correct
29 Correct 32 ms 33548 KB Output is correct
30 Correct 29 ms 33548 KB Output is correct
31 Correct 44 ms 33548 KB Output is correct
32 Correct 32 ms 33548 KB Output is correct
33 Correct 29 ms 33548 KB Output is correct
34 Correct 28 ms 33548 KB Output is correct
35 Correct 30 ms 33548 KB Output is correct
36 Correct 30 ms 33548 KB Output is correct
37 Correct 34 ms 33548 KB Output is correct
38 Correct 35 ms 33548 KB Output is correct
39 Correct 32 ms 33548 KB Output is correct
40 Correct 31 ms 33548 KB Output is correct
41 Correct 31 ms 33548 KB Output is correct
42 Correct 38 ms 33548 KB Output is correct
43 Correct 31 ms 33548 KB Output is correct
44 Correct 30 ms 33548 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33144 KB Output is correct
2 Correct 27 ms 33252 KB Output is correct
3 Correct 33 ms 33328 KB Output is correct
4 Correct 28 ms 33344 KB Output is correct
5 Correct 26 ms 33380 KB Output is correct
6 Correct 27 ms 33380 KB Output is correct
7 Correct 26 ms 33380 KB Output is correct
8 Correct 26 ms 33380 KB Output is correct
9 Correct 27 ms 33456 KB Output is correct
10 Correct 27 ms 33456 KB Output is correct
11 Correct 26 ms 33456 KB Output is correct
12 Correct 27 ms 33456 KB Output is correct
13 Correct 28 ms 33456 KB Output is correct
14 Correct 25 ms 33456 KB Output is correct
15 Correct 28 ms 33456 KB Output is correct
16 Correct 26 ms 33456 KB Output is correct
17 Correct 26 ms 33456 KB Output is correct
18 Correct 26 ms 33516 KB Output is correct
19 Correct 27 ms 33516 KB Output is correct
20 Correct 30 ms 33548 KB Output is correct
21 Correct 26 ms 33548 KB Output is correct
22 Correct 26 ms 33548 KB Output is correct
23 Correct 29 ms 33548 KB Output is correct
24 Correct 26 ms 33548 KB Output is correct
25 Correct 40 ms 33548 KB Output is correct
26 Correct 30 ms 33548 KB Output is correct
27 Correct 33 ms 33548 KB Output is correct
28 Correct 34 ms 33548 KB Output is correct
29 Correct 32 ms 33548 KB Output is correct
30 Correct 29 ms 33548 KB Output is correct
31 Correct 44 ms 33548 KB Output is correct
32 Correct 32 ms 33548 KB Output is correct
33 Correct 29 ms 33548 KB Output is correct
34 Correct 28 ms 33548 KB Output is correct
35 Correct 30 ms 33548 KB Output is correct
36 Correct 30 ms 33548 KB Output is correct
37 Correct 34 ms 33548 KB Output is correct
38 Correct 35 ms 33548 KB Output is correct
39 Correct 32 ms 33548 KB Output is correct
40 Correct 31 ms 33548 KB Output is correct
41 Correct 31 ms 33548 KB Output is correct
42 Correct 38 ms 33548 KB Output is correct
43 Correct 31 ms 33548 KB Output is correct
44 Correct 30 ms 33548 KB Output is correct
45 Correct 335 ms 36092 KB Output is correct
46 Correct 340 ms 36092 KB Output is correct
47 Correct 344 ms 36092 KB Output is correct
48 Correct 356 ms 36092 KB Output is correct
49 Correct 338 ms 36092 KB Output is correct
50 Correct 186 ms 36092 KB Output is correct
51 Correct 170 ms 36092 KB Output is correct
52 Correct 324 ms 36092 KB Output is correct
53 Correct 342 ms 36232 KB Output is correct
54 Correct 195 ms 36232 KB Output is correct
55 Correct 174 ms 36232 KB Output is correct
56 Correct 167 ms 36232 KB Output is correct
57 Correct 313 ms 36232 KB Output is correct
58 Correct 347 ms 36232 KB Output is correct
59 Correct 313 ms 36232 KB Output is correct
60 Correct 339 ms 36232 KB Output is correct
61 Correct 340 ms 36232 KB Output is correct
62 Correct 369 ms 36232 KB Output is correct
63 Correct 162 ms 36232 KB Output is correct
64 Correct 179 ms 36232 KB Output is correct
65 Correct 181 ms 36232 KB Output is correct
66 Correct 180 ms 36232 KB Output is correct
67 Correct 322 ms 36584 KB Output is correct
68 Correct 322 ms 36600 KB Output is correct
69 Correct 311 ms 36732 KB Output is correct
70 Correct 331 ms 36812 KB Output is correct
71 Correct 545 ms 36812 KB Output is correct
72 Correct 315 ms 36812 KB Output is correct
73 Correct 443 ms 36812 KB Output is correct
74 Correct 322 ms 36828 KB Output is correct
75 Correct 301 ms 36828 KB Output is correct
76 Correct 303 ms 36828 KB Output is correct
77 Correct 308 ms 36828 KB Output is correct
78 Correct 340 ms 36828 KB Output is correct
79 Correct 332 ms 36828 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33144 KB Output is correct
2 Correct 27 ms 33252 KB Output is correct
3 Correct 33 ms 33328 KB Output is correct
4 Correct 28 ms 33344 KB Output is correct
5 Correct 26 ms 33380 KB Output is correct
6 Correct 27 ms 33380 KB Output is correct
7 Correct 26 ms 33380 KB Output is correct
8 Correct 26 ms 33380 KB Output is correct
9 Correct 27 ms 33456 KB Output is correct
10 Correct 27 ms 33456 KB Output is correct
11 Correct 26 ms 33456 KB Output is correct
12 Correct 27 ms 33456 KB Output is correct
13 Correct 28 ms 33456 KB Output is correct
14 Correct 25 ms 33456 KB Output is correct
15 Correct 28 ms 33456 KB Output is correct
16 Correct 26 ms 33456 KB Output is correct
17 Correct 26 ms 33456 KB Output is correct
18 Correct 26 ms 33516 KB Output is correct
19 Correct 27 ms 33516 KB Output is correct
20 Correct 30 ms 33548 KB Output is correct
21 Correct 26 ms 33548 KB Output is correct
22 Correct 26 ms 33548 KB Output is correct
23 Correct 29 ms 33548 KB Output is correct
24 Correct 26 ms 33548 KB Output is correct
25 Correct 40 ms 33548 KB Output is correct
26 Correct 30 ms 33548 KB Output is correct
27 Correct 33 ms 33548 KB Output is correct
28 Correct 34 ms 33548 KB Output is correct
29 Correct 32 ms 33548 KB Output is correct
30 Correct 29 ms 33548 KB Output is correct
31 Correct 44 ms 33548 KB Output is correct
32 Correct 32 ms 33548 KB Output is correct
33 Correct 29 ms 33548 KB Output is correct
34 Correct 28 ms 33548 KB Output is correct
35 Correct 30 ms 33548 KB Output is correct
36 Correct 30 ms 33548 KB Output is correct
37 Correct 34 ms 33548 KB Output is correct
38 Correct 35 ms 33548 KB Output is correct
39 Correct 32 ms 33548 KB Output is correct
40 Correct 31 ms 33548 KB Output is correct
41 Correct 31 ms 33548 KB Output is correct
42 Correct 38 ms 33548 KB Output is correct
43 Correct 31 ms 33548 KB Output is correct
44 Correct 30 ms 33548 KB Output is correct
45 Correct 335 ms 36092 KB Output is correct
46 Correct 340 ms 36092 KB Output is correct
47 Correct 344 ms 36092 KB Output is correct
48 Correct 356 ms 36092 KB Output is correct
49 Correct 338 ms 36092 KB Output is correct
50 Correct 186 ms 36092 KB Output is correct
51 Correct 170 ms 36092 KB Output is correct
52 Correct 324 ms 36092 KB Output is correct
53 Correct 342 ms 36232 KB Output is correct
54 Correct 195 ms 36232 KB Output is correct
55 Correct 174 ms 36232 KB Output is correct
56 Correct 167 ms 36232 KB Output is correct
57 Correct 313 ms 36232 KB Output is correct
58 Correct 347 ms 36232 KB Output is correct
59 Correct 313 ms 36232 KB Output is correct
60 Correct 339 ms 36232 KB Output is correct
61 Correct 340 ms 36232 KB Output is correct
62 Correct 369 ms 36232 KB Output is correct
63 Correct 162 ms 36232 KB Output is correct
64 Correct 179 ms 36232 KB Output is correct
65 Correct 181 ms 36232 KB Output is correct
66 Correct 180 ms 36232 KB Output is correct
67 Correct 322 ms 36584 KB Output is correct
68 Correct 322 ms 36600 KB Output is correct
69 Correct 311 ms 36732 KB Output is correct
70 Correct 331 ms 36812 KB Output is correct
71 Correct 545 ms 36812 KB Output is correct
72 Correct 315 ms 36812 KB Output is correct
73 Correct 443 ms 36812 KB Output is correct
74 Correct 322 ms 36828 KB Output is correct
75 Correct 301 ms 36828 KB Output is correct
76 Correct 303 ms 36828 KB Output is correct
77 Correct 308 ms 36828 KB Output is correct
78 Correct 340 ms 36828 KB Output is correct
79 Correct 332 ms 36828 KB Output is correct
80 Correct 4122 ms 57356 KB Output is correct
81 Correct 4367 ms 57356 KB Output is correct
82 Correct 4394 ms 57356 KB Output is correct
83 Correct 4352 ms 57356 KB Output is correct
84 Correct 4327 ms 57356 KB Output is correct
85 Correct 2099 ms 57356 KB Output is correct
86 Correct 1919 ms 57356 KB Output is correct
87 Correct 3809 ms 57356 KB Output is correct
88 Correct 4851 ms 59536 KB Output is correct
89 Correct 2851 ms 59536 KB Output is correct
90 Correct 2475 ms 59536 KB Output is correct
91 Correct 2386 ms 59536 KB Output is correct
92 Correct 4299 ms 59536 KB Output is correct
93 Correct 4019 ms 59536 KB Output is correct
94 Correct 4341 ms 59536 KB Output is correct
95 Correct 4450 ms 59536 KB Output is correct
96 Correct 4146 ms 59536 KB Output is correct
97 Correct 2825 ms 59536 KB Output is correct
98 Correct 2418 ms 59536 KB Output is correct
99 Correct 1901 ms 59536 KB Output is correct
100 Correct 2553 ms 59536 KB Output is correct
101 Correct 2525 ms 69896 KB Output is correct
102 Correct 4267 ms 90868 KB Output is correct
103 Correct 4149 ms 107028 KB Output is correct
104 Correct 4275 ms 122340 KB Output is correct
105 Correct 4209 ms 135780 KB Output is correct
106 Correct 4294 ms 150656 KB Output is correct
107 Correct 4339 ms 165236 KB Output is correct
108 Correct 4124 ms 181488 KB Output is correct
109 Correct 4093 ms 195860 KB Output is correct
110 Correct 3804 ms 200964 KB Output is correct
111 Correct 3634 ms 215688 KB Output is correct
112 Correct 3584 ms 229108 KB Output is correct
113 Correct 4174 ms 246916 KB Output is correct
114 Correct 4374 ms 261384 KB Output is correct