Submission #46576

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
46576	2018-04-21T14:05:23 Z	maksim_gaponov	Port Facility (JOI17_port_facility)	C++14	78 / 100	6000 ms	304592 KB

port_facility

#define _CRT_SECURE_NO_WARNINGS
#ifdef _DEBUG
#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 _DEBUG
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

const int MAXN = 10485760;
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];

struct Action {
	int id;
	int time;
	bool type;

	Action() {}

	Action(int id, int time, bool type) : id(id), time(time), type(type) {}
};

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

bool operator<(const Action& a1, const Action& a2) {
	return a1.time < a2.time;
}

bool get_bit(int mask, int i) {
	return mask & (1 << i);
}

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();
	memset(color, 0, sizeof(color));
	int n;
	scanf("%d", &n);
	for (int i = 0; i < 5 * 2 * n; i++) {
		max_end[i] = -1;
		min_start[i] = -1;
	}
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &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[2 * i] = Action(i, segment_start[i], true);
		actions[2 * i + 1] = Action(i, segment_end[i], false);
	}
	int ans = 1;
	int itr = 0;
	while (true) {
		while (used[itr])
			itr++;
		if (itr == n)
			break;
		ans *= 2;
		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);
			}
		}
	}
	sort(actions, actions + 2 * n);
	for (int i = 0; i < 2 * n; i++) {
		Action act = actions[i];
		if (act.type) {
			v[(color[act.id] + 1) / 2].push_back(act.id);
		}
		else {
			if (v[(color[act.id] + 1) / 2].back() != act.id) {
				printf("0");
				return 0;
			}
			v[(color[act.id] + 1) / 2].pop_back();
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message

port_facility.cpp: In function 'int main()':
port_facility.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
port_facility.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &segment_start[i], &segment_end[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	41464 KB	Output is correct
2	Correct	31 ms	41576 KB	Output is correct
3	Correct	32 ms	41576 KB	Output is correct
4	Correct	31 ms	41576 KB	Output is correct
5	Correct	31 ms	41576 KB	Output is correct
6	Correct	31 ms	41576 KB	Output is correct
7	Correct	32 ms	41692 KB	Output is correct
8	Correct	31 ms	41692 KB	Output is correct
9	Correct	31 ms	41692 KB	Output is correct
10	Correct	32 ms	41692 KB	Output is correct
11	Correct	32 ms	41692 KB	Output is correct
12	Correct	32 ms	41692 KB	Output is correct
13	Correct	32 ms	41692 KB	Output is correct
14	Correct	31 ms	41692 KB	Output is correct
15	Correct	31 ms	41708 KB	Output is correct
16	Correct	32 ms	41708 KB	Output is correct
17	Correct	33 ms	41852 KB	Output is correct
18	Correct	33 ms	41852 KB	Output is correct
19	Correct	32 ms	41852 KB	Output is correct
20	Correct	32 ms	41852 KB	Output is correct
21	Correct	32 ms	41852 KB	Output is correct
22	Correct	31 ms	41852 KB	Output is correct
23	Correct	32 ms	41852 KB	Output is correct
24	Correct	32 ms	41852 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	41464 KB	Output is correct
2	Correct	31 ms	41576 KB	Output is correct
3	Correct	32 ms	41576 KB	Output is correct
4	Correct	31 ms	41576 KB	Output is correct
5	Correct	31 ms	41576 KB	Output is correct
6	Correct	31 ms	41576 KB	Output is correct
7	Correct	32 ms	41692 KB	Output is correct
8	Correct	31 ms	41692 KB	Output is correct
9	Correct	31 ms	41692 KB	Output is correct
10	Correct	32 ms	41692 KB	Output is correct
11	Correct	32 ms	41692 KB	Output is correct
12	Correct	32 ms	41692 KB	Output is correct
13	Correct	32 ms	41692 KB	Output is correct
14	Correct	31 ms	41692 KB	Output is correct
15	Correct	31 ms	41708 KB	Output is correct
16	Correct	32 ms	41708 KB	Output is correct
17	Correct	33 ms	41852 KB	Output is correct
18	Correct	33 ms	41852 KB	Output is correct
19	Correct	32 ms	41852 KB	Output is correct
20	Correct	32 ms	41852 KB	Output is correct
21	Correct	32 ms	41852 KB	Output is correct
22	Correct	31 ms	41852 KB	Output is correct
23	Correct	32 ms	41852 KB	Output is correct
24	Correct	32 ms	41852 KB	Output is correct
25	Correct	36 ms	41852 KB	Output is correct
26	Correct	36 ms	41852 KB	Output is correct
27	Correct	67 ms	41916 KB	Output is correct
28	Correct	35 ms	41916 KB	Output is correct
29	Correct	36 ms	41916 KB	Output is correct
30	Correct	35 ms	41916 KB	Output is correct
31	Correct	37 ms	41916 KB	Output is correct
32	Correct	35 ms	41916 KB	Output is correct
33	Correct	36 ms	41916 KB	Output is correct
34	Correct	39 ms	41980 KB	Output is correct
35	Correct	35 ms	41980 KB	Output is correct
36	Correct	41 ms	41980 KB	Output is correct
37	Correct	36 ms	41980 KB	Output is correct
38	Correct	37 ms	41980 KB	Output is correct
39	Correct	41 ms	41980 KB	Output is correct
40	Correct	37 ms	41980 KB	Output is correct
41	Correct	44 ms	41980 KB	Output is correct
42	Correct	35 ms	41980 KB	Output is correct
43	Correct	73 ms	41980 KB	Output is correct
44	Correct	37 ms	41980 KB	Output is correct

Subtask #3
56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	41464 KB	Output is correct
2	Correct	31 ms	41576 KB	Output is correct
3	Correct	32 ms	41576 KB	Output is correct
4	Correct	31 ms	41576 KB	Output is correct
5	Correct	31 ms	41576 KB	Output is correct
6	Correct	31 ms	41576 KB	Output is correct
7	Correct	32 ms	41692 KB	Output is correct
8	Correct	31 ms	41692 KB	Output is correct
9	Correct	31 ms	41692 KB	Output is correct
10	Correct	32 ms	41692 KB	Output is correct
11	Correct	32 ms	41692 KB	Output is correct
12	Correct	32 ms	41692 KB	Output is correct
13	Correct	32 ms	41692 KB	Output is correct
14	Correct	31 ms	41692 KB	Output is correct
15	Correct	31 ms	41708 KB	Output is correct
16	Correct	32 ms	41708 KB	Output is correct
17	Correct	33 ms	41852 KB	Output is correct
18	Correct	33 ms	41852 KB	Output is correct
19	Correct	32 ms	41852 KB	Output is correct
20	Correct	32 ms	41852 KB	Output is correct
21	Correct	32 ms	41852 KB	Output is correct
22	Correct	31 ms	41852 KB	Output is correct
23	Correct	32 ms	41852 KB	Output is correct
24	Correct	32 ms	41852 KB	Output is correct
25	Correct	36 ms	41852 KB	Output is correct
26	Correct	36 ms	41852 KB	Output is correct
27	Correct	67 ms	41916 KB	Output is correct
28	Correct	35 ms	41916 KB	Output is correct
29	Correct	36 ms	41916 KB	Output is correct
30	Correct	35 ms	41916 KB	Output is correct
31	Correct	37 ms	41916 KB	Output is correct
32	Correct	35 ms	41916 KB	Output is correct
33	Correct	36 ms	41916 KB	Output is correct
34	Correct	39 ms	41980 KB	Output is correct
35	Correct	35 ms	41980 KB	Output is correct
36	Correct	41 ms	41980 KB	Output is correct
37	Correct	36 ms	41980 KB	Output is correct
38	Correct	37 ms	41980 KB	Output is correct
39	Correct	41 ms	41980 KB	Output is correct
40	Correct	37 ms	41980 KB	Output is correct
41	Correct	44 ms	41980 KB	Output is correct
42	Correct	35 ms	41980 KB	Output is correct
43	Correct	73 ms	41980 KB	Output is correct
44	Correct	37 ms	41980 KB	Output is correct
45	Correct	371 ms	53120 KB	Output is correct
46	Correct	365 ms	53120 KB	Output is correct
47	Correct	364 ms	53120 KB	Output is correct
48	Correct	386 ms	53140 KB	Output is correct
49	Correct	365 ms	53140 KB	Output is correct
50	Correct	392 ms	53140 KB	Output is correct
51	Correct	423 ms	53140 KB	Output is correct
52	Correct	350 ms	53140 KB	Output is correct
53	Correct	349 ms	53496 KB	Output is correct
54	Correct	524 ms	54084 KB	Output is correct
55	Correct	489 ms	54084 KB	Output is correct
56	Correct	552 ms	54084 KB	Output is correct
57	Correct	325 ms	54084 KB	Output is correct
58	Correct	366 ms	54084 KB	Output is correct
59	Correct	372 ms	54084 KB	Output is correct
60	Correct	370 ms	54084 KB	Output is correct
61	Correct	359 ms	54084 KB	Output is correct
62	Correct	409 ms	54084 KB	Output is correct
63	Correct	391 ms	54084 KB	Output is correct
64	Correct	383 ms	54084 KB	Output is correct
65	Correct	647 ms	54084 KB	Output is correct
66	Correct	602 ms	54084 KB	Output is correct
67	Correct	360 ms	54084 KB	Output is correct
68	Correct	329 ms	54084 KB	Output is correct
69	Correct	327 ms	54084 KB	Output is correct
70	Correct	347 ms	54084 KB	Output is correct
71	Correct	348 ms	54084 KB	Output is correct
72	Correct	335 ms	54084 KB	Output is correct
73	Correct	319 ms	54084 KB	Output is correct
74	Correct	318 ms	54084 KB	Output is correct
75	Correct	309 ms	54084 KB	Output is correct
76	Correct	317 ms	54084 KB	Output is correct
77	Correct	307 ms	54084 KB	Output is correct
78	Correct	353 ms	54084 KB	Output is correct
79	Correct	374 ms	54084 KB	Output is correct

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	41464 KB	Output is correct
2	Correct	31 ms	41576 KB	Output is correct
3	Correct	32 ms	41576 KB	Output is correct
4	Correct	31 ms	41576 KB	Output is correct
5	Correct	31 ms	41576 KB	Output is correct
6	Correct	31 ms	41576 KB	Output is correct
7	Correct	32 ms	41692 KB	Output is correct
8	Correct	31 ms	41692 KB	Output is correct
9	Correct	31 ms	41692 KB	Output is correct
10	Correct	32 ms	41692 KB	Output is correct
11	Correct	32 ms	41692 KB	Output is correct
12	Correct	32 ms	41692 KB	Output is correct
13	Correct	32 ms	41692 KB	Output is correct
14	Correct	31 ms	41692 KB	Output is correct
15	Correct	31 ms	41708 KB	Output is correct
16	Correct	32 ms	41708 KB	Output is correct
17	Correct	33 ms	41852 KB	Output is correct
18	Correct	33 ms	41852 KB	Output is correct
19	Correct	32 ms	41852 KB	Output is correct
20	Correct	32 ms	41852 KB	Output is correct
21	Correct	32 ms	41852 KB	Output is correct
22	Correct	31 ms	41852 KB	Output is correct
23	Correct	32 ms	41852 KB	Output is correct
24	Correct	32 ms	41852 KB	Output is correct
25	Correct	36 ms	41852 KB	Output is correct
26	Correct	36 ms	41852 KB	Output is correct
27	Correct	67 ms	41916 KB	Output is correct
28	Correct	35 ms	41916 KB	Output is correct
29	Correct	36 ms	41916 KB	Output is correct
30	Correct	35 ms	41916 KB	Output is correct
31	Correct	37 ms	41916 KB	Output is correct
32	Correct	35 ms	41916 KB	Output is correct
33	Correct	36 ms	41916 KB	Output is correct
34	Correct	39 ms	41980 KB	Output is correct
35	Correct	35 ms	41980 KB	Output is correct
36	Correct	41 ms	41980 KB	Output is correct
37	Correct	36 ms	41980 KB	Output is correct
38	Correct	37 ms	41980 KB	Output is correct
39	Correct	41 ms	41980 KB	Output is correct
40	Correct	37 ms	41980 KB	Output is correct
41	Correct	44 ms	41980 KB	Output is correct
42	Correct	35 ms	41980 KB	Output is correct
43	Correct	73 ms	41980 KB	Output is correct
44	Correct	37 ms	41980 KB	Output is correct
45	Correct	371 ms	53120 KB	Output is correct
46	Correct	365 ms	53120 KB	Output is correct
47	Correct	364 ms	53120 KB	Output is correct
48	Correct	386 ms	53140 KB	Output is correct
49	Correct	365 ms	53140 KB	Output is correct
50	Correct	392 ms	53140 KB	Output is correct
51	Correct	423 ms	53140 KB	Output is correct
52	Correct	350 ms	53140 KB	Output is correct
53	Correct	349 ms	53496 KB	Output is correct
54	Correct	524 ms	54084 KB	Output is correct
55	Correct	489 ms	54084 KB	Output is correct
56	Correct	552 ms	54084 KB	Output is correct
57	Correct	325 ms	54084 KB	Output is correct
58	Correct	366 ms	54084 KB	Output is correct
59	Correct	372 ms	54084 KB	Output is correct
60	Correct	370 ms	54084 KB	Output is correct
61	Correct	359 ms	54084 KB	Output is correct
62	Correct	409 ms	54084 KB	Output is correct
63	Correct	391 ms	54084 KB	Output is correct
64	Correct	383 ms	54084 KB	Output is correct
65	Correct	647 ms	54084 KB	Output is correct
66	Correct	602 ms	54084 KB	Output is correct
67	Correct	360 ms	54084 KB	Output is correct
68	Correct	329 ms	54084 KB	Output is correct
69	Correct	327 ms	54084 KB	Output is correct
70	Correct	347 ms	54084 KB	Output is correct
71	Correct	348 ms	54084 KB	Output is correct
72	Correct	335 ms	54084 KB	Output is correct
73	Correct	319 ms	54084 KB	Output is correct
74	Correct	318 ms	54084 KB	Output is correct
75	Correct	309 ms	54084 KB	Output is correct
76	Correct	317 ms	54084 KB	Output is correct
77	Correct	307 ms	54084 KB	Output is correct
78	Correct	353 ms	54084 KB	Output is correct
79	Correct	374 ms	54084 KB	Output is correct
80	Correct	4722 ms	169004 KB	Output is correct
81	Correct	4637 ms	183544 KB	Output is correct
82	Correct	4820 ms	198188 KB	Output is correct
83	Correct	4923 ms	212684 KB	Output is correct
84	Correct	5049 ms	227280 KB	Output is correct
85	Correct	5166 ms	241980 KB	Output is correct
86	Correct	4977 ms	256608 KB	Output is correct
87	Correct	4295 ms	269112 KB	Output is correct
88	Correct	5094 ms	287940 KB	Output is correct
89	Execution timed out	6039 ms	304592 KB	Time limit exceeded
90	Halted	0 ms	0 KB	-

Submission #46576

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 56.0 / 56.0

Subtask #4 0 / 22.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
56.0 / 56.0

Subtask #4
0 / 22.0