Submission #23709

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
23709	2017-05-22T10:30:04 Z	rubabredwan	Port Facility (JOI17_port_facility)	C++14	100 / 100	2916 ms	322216 KB

port_facility

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 2000005;
const int oo = 1e9;

void scanF(int &x){
	register int c = getchar_unlocked();
	x = 0;
	for(;(c<48 || c>57);c = getchar_unlocked());
	for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c - 48;}
}

int n, st[N], en[N];
int lf[N], rf[N], idx[N];
int col[N], vis[N];

struct segtree{
	int n; 
	pii mn[N*4], mx[N*4];
	void build(int _n){
		n = 2 * _n;
		for(int i = 1; i <= n; i++){
			mn[i + n - 1] = {lf[i], idx[i]};
			mx[i + n - 1] = {rf[i], idx[i]};
		}
		for(int i = n - 1; i > 0; --i){ 
			mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
			mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
		}
	}
	void modify(int pos){
		pos = pos - 1 + n;
		mn[pos] = {+oo, +oo};
		mx[pos] = {-oo, -oo};
		while(pos > 1){
			mn[pos >> 1] = min(mn[pos], mn[pos ^ 1]);
			mx[pos >> 1] = max(mx[pos], mx[pos ^ 1]);
			pos >>= 1;
		}
	}
	pii query_max(int l, int r){;
		--l;
		pii ret = {-oo, -oo};
		for(l += n, r += n; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = max(ret, mx[l++]);
			if(r & 1) ret = max(ret, mx[--r]);
		}
		return ret;
	}
	pii query_min(int l, int r){;
		--l;
		pii ret = {+oo, +oo};
		for(l += n, r += n; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = min(ret, mn[l++]);
			if(r & 1) ret = min(ret, mn[--r]);
		}
		return ret;
	}
} tree;

void dfs(int at){
	vis[at] = 1;
	tree.modify(st[at]);
	tree.modify(en[at]);
	while(1){
		pii f = tree.query_min(st[at], en[at]);
		if(f.first >= st[at]) break;
		col[f.second] = col[at] ^ 1;
		dfs(f.second);
	}
	while(1){
		pii f = tree.query_max(st[at], en[at]);
		if(f.first <= en[at]) break;
		col[f.second] = col[at] ^ 1;
		dfs(f.second);
	}
}

vector<int>g[N];
int flag;
int t[N*4];

void update(int b, int e, int node, int pos, int val){
	if(b == e){
		t[node] ^= (1 << val);
		return;
	}
	int mid = (b + e) / 2, l = 2 * node, h = l + 1;
	if(pos <= mid) update(b, mid, l, pos, val);
	else update(mid+1, e, h, pos, val);
	t[node] = t[l] | t[h];
}

int get(int b, int e, int node, int x, int y){
	if(y < b ||e < x) return 0;
	if(b >= x && e <= y) return t[node];
	int mid = (b + e) / 2, l = 2 * node, h = l + 1;
	return get(b, mid, l, x, y) | get(mid+1, e, h, x, y);
}

bool check(){
	for(int i=1;i<=n+n;i++){
		if(st[idx[i]] == i){
			update(1, n+n, 1, st[idx[i]], col[idx[i]]);
		}
		else{
			int g1 = get(1, n+n, 1, st[idx[i]]+1, en[idx[i]]);
			int g2 = 1 << col[idx[i]];
			if(g1 & g2) return false;
			update(1, n+n, 1, st[idx[i]], col[idx[i]]);
		}
	}
	return true;
}

int main(){
	scanF(n);
	for(int i=1;i<=n;i++){
		scanF(st[i]);
		scanF(en[i]);
		lf[en[i]] = st[i];
		lf[st[i]] = +oo;
		rf[st[i]] = en[i];
		rf[en[i]] = -oo;
		idx[st[i]] = i;
		idx[en[i]] = i;
	}
	tree.build(n);
	int comp = 0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			++comp;
		}
	}
	if(check() == false) printf("0\n");
	else{
		long long ret = 1LL;
		long long mod = 1e9 + 7;
		for(int i=1;i<=comp;i++){
			ret *= 2LL;
			ret %= mod;
		}
		printf("%lld\n", ret);
	}
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	259836 KB	Output is correct
2	Correct	26 ms	259836 KB	Output is correct
3	Correct	19 ms	259836 KB	Output is correct
4	Correct	13 ms	259836 KB	Output is correct
5	Correct	13 ms	259836 KB	Output is correct
6	Correct	23 ms	259836 KB	Output is correct
7	Correct	16 ms	259836 KB	Output is correct
8	Correct	29 ms	259836 KB	Output is correct
9	Correct	39 ms	259836 KB	Output is correct
10	Correct	29 ms	259836 KB	Output is correct
11	Correct	13 ms	259836 KB	Output is correct
12	Correct	23 ms	259836 KB	Output is correct
13	Correct	26 ms	259836 KB	Output is correct
14	Correct	16 ms	259836 KB	Output is correct
15	Correct	26 ms	259836 KB	Output is correct
16	Correct	23 ms	259836 KB	Output is correct
17	Correct	6 ms	259836 KB	Output is correct
18	Correct	13 ms	259836 KB	Output is correct
19	Correct	23 ms	259836 KB	Output is correct
20	Correct	19 ms	259836 KB	Output is correct
21	Correct	29 ms	259836 KB	Output is correct
22	Correct	19 ms	259836 KB	Output is correct
23	Correct	19 ms	259836 KB	Output is correct
24	Correct	29 ms	259836 KB	Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	259836 KB	Output is correct
2	Correct	26 ms	259836 KB	Output is correct
3	Correct	19 ms	259836 KB	Output is correct
4	Correct	13 ms	259836 KB	Output is correct
5	Correct	13 ms	259836 KB	Output is correct
6	Correct	23 ms	259836 KB	Output is correct
7	Correct	16 ms	259836 KB	Output is correct
8	Correct	29 ms	259836 KB	Output is correct
9	Correct	39 ms	259836 KB	Output is correct
10	Correct	29 ms	259836 KB	Output is correct
11	Correct	13 ms	259836 KB	Output is correct
12	Correct	23 ms	259836 KB	Output is correct
13	Correct	26 ms	259836 KB	Output is correct
14	Correct	16 ms	259836 KB	Output is correct
15	Correct	26 ms	259836 KB	Output is correct
16	Correct	23 ms	259836 KB	Output is correct
17	Correct	6 ms	259836 KB	Output is correct
18	Correct	13 ms	259836 KB	Output is correct
19	Correct	23 ms	259836 KB	Output is correct
20	Correct	19 ms	259836 KB	Output is correct
21	Correct	29 ms	259836 KB	Output is correct
22	Correct	19 ms	259836 KB	Output is correct
23	Correct	19 ms	259836 KB	Output is correct
24	Correct	29 ms	259836 KB	Output is correct
25	Correct	19 ms	259836 KB	Output is correct
26	Correct	26 ms	259836 KB	Output is correct
27	Correct	19 ms	259836 KB	Output is correct
28	Correct	26 ms	259836 KB	Output is correct
29	Correct	36 ms	259836 KB	Output is correct
30	Correct	26 ms	259836 KB	Output is correct
31	Correct	29 ms	259836 KB	Output is correct
32	Correct	19 ms	259836 KB	Output is correct
33	Correct	13 ms	259836 KB	Output is correct
34	Correct	26 ms	259836 KB	Output is correct
35	Correct	23 ms	259836 KB	Output is correct
36	Correct	19 ms	259836 KB	Output is correct
37	Correct	19 ms	259836 KB	Output is correct
38	Correct	16 ms	259836 KB	Output is correct
39	Correct	19 ms	259836 KB	Output is correct
40	Correct	23 ms	259836 KB	Output is correct
41	Correct	23 ms	259840 KB	Output is correct
42	Correct	29 ms	259836 KB	Output is correct
43	Correct	26 ms	259836 KB	Output is correct
44	Correct	16 ms	259836 KB	Output is correct
45	Correct	183 ms	260600 KB	Output is correct
46	Correct	213 ms	261428 KB	Output is correct
47	Correct	206 ms	260028 KB	Output is correct
48	Correct	206 ms	261404 KB	Output is correct
49	Correct	229 ms	260144 KB	Output is correct
50	Correct	223 ms	261192 KB	Output is correct
51	Correct	159 ms	261148 KB	Output is correct
52	Correct	153 ms	259836 KB	Output is correct
53	Correct	213 ms	259836 KB	Output is correct
54	Correct	129 ms	265960 KB	Output is correct
55	Correct	129 ms	262832 KB	Output is correct
56	Correct	146 ms	262840 KB	Output is correct
57	Correct	156 ms	259836 KB	Output is correct
58	Correct	183 ms	259836 KB	Output is correct
59	Correct	199 ms	259836 KB	Output is correct
60	Correct	203 ms	259836 KB	Output is correct
61	Correct	223 ms	259836 KB	Output is correct
62	Correct	153 ms	259836 KB	Output is correct
63	Correct	143 ms	259836 KB	Output is correct
64	Correct	123 ms	259836 KB	Output is correct
65	Correct	186 ms	265960 KB	Output is correct
66	Correct	199 ms	265960 KB	Output is correct
67	Correct	209 ms	262832 KB	Output is correct
68	Correct	209 ms	262832 KB	Output is correct
69	Correct	223 ms	262496 KB	Output is correct
70	Correct	219 ms	262484 KB	Output is correct
71	Correct	209 ms	265956 KB	Output is correct
72	Correct	186 ms	265960 KB	Output is correct
73	Correct	209 ms	263880 KB	Output is correct
74	Correct	193 ms	263880 KB	Output is correct
75	Correct	159 ms	263432 KB	Output is correct
76	Correct	146 ms	265964 KB	Output is correct
77	Correct	106 ms	265964 KB	Output is correct
78	Correct	236 ms	261228 KB	Output is correct
79	Correct	206 ms	260664 KB	Output is correct

Subtask #4
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	259836 KB	Output is correct
2	Correct	26 ms	259836 KB	Output is correct
3	Correct	19 ms	259836 KB	Output is correct
4	Correct	13 ms	259836 KB	Output is correct
5	Correct	13 ms	259836 KB	Output is correct
6	Correct	23 ms	259836 KB	Output is correct
7	Correct	16 ms	259836 KB	Output is correct
8	Correct	29 ms	259836 KB	Output is correct
9	Correct	39 ms	259836 KB	Output is correct
10	Correct	29 ms	259836 KB	Output is correct
11	Correct	13 ms	259836 KB	Output is correct
12	Correct	23 ms	259836 KB	Output is correct
13	Correct	26 ms	259836 KB	Output is correct
14	Correct	16 ms	259836 KB	Output is correct
15	Correct	26 ms	259836 KB	Output is correct
16	Correct	23 ms	259836 KB	Output is correct
17	Correct	6 ms	259836 KB	Output is correct
18	Correct	13 ms	259836 KB	Output is correct
19	Correct	23 ms	259836 KB	Output is correct
20	Correct	19 ms	259836 KB	Output is correct
21	Correct	29 ms	259836 KB	Output is correct
22	Correct	19 ms	259836 KB	Output is correct
23	Correct	19 ms	259836 KB	Output is correct
24	Correct	29 ms	259836 KB	Output is correct
25	Correct	19 ms	259836 KB	Output is correct
26	Correct	26 ms	259836 KB	Output is correct
27	Correct	19 ms	259836 KB	Output is correct
28	Correct	26 ms	259836 KB	Output is correct
29	Correct	36 ms	259836 KB	Output is correct
30	Correct	26 ms	259836 KB	Output is correct
31	Correct	29 ms	259836 KB	Output is correct
32	Correct	19 ms	259836 KB	Output is correct
33	Correct	13 ms	259836 KB	Output is correct
34	Correct	26 ms	259836 KB	Output is correct
35	Correct	23 ms	259836 KB	Output is correct
36	Correct	19 ms	259836 KB	Output is correct
37	Correct	19 ms	259836 KB	Output is correct
38	Correct	16 ms	259836 KB	Output is correct
39	Correct	19 ms	259836 KB	Output is correct
40	Correct	23 ms	259836 KB	Output is correct
41	Correct	23 ms	259840 KB	Output is correct
42	Correct	29 ms	259836 KB	Output is correct
43	Correct	26 ms	259836 KB	Output is correct
44	Correct	16 ms	259836 KB	Output is correct
45	Correct	183 ms	260600 KB	Output is correct
46	Correct	213 ms	261428 KB	Output is correct
47	Correct	206 ms	260028 KB	Output is correct
48	Correct	206 ms	261404 KB	Output is correct
49	Correct	229 ms	260144 KB	Output is correct
50	Correct	223 ms	261192 KB	Output is correct
51	Correct	159 ms	261148 KB	Output is correct
52	Correct	153 ms	259836 KB	Output is correct
53	Correct	213 ms	259836 KB	Output is correct
54	Correct	129 ms	265960 KB	Output is correct
55	Correct	129 ms	262832 KB	Output is correct
56	Correct	146 ms	262840 KB	Output is correct
57	Correct	156 ms	259836 KB	Output is correct
58	Correct	183 ms	259836 KB	Output is correct
59	Correct	199 ms	259836 KB	Output is correct
60	Correct	203 ms	259836 KB	Output is correct
61	Correct	223 ms	259836 KB	Output is correct
62	Correct	153 ms	259836 KB	Output is correct
63	Correct	143 ms	259836 KB	Output is correct
64	Correct	123 ms	259836 KB	Output is correct
65	Correct	186 ms	265960 KB	Output is correct
66	Correct	199 ms	265960 KB	Output is correct
67	Correct	209 ms	262832 KB	Output is correct
68	Correct	209 ms	262832 KB	Output is correct
69	Correct	223 ms	262496 KB	Output is correct
70	Correct	219 ms	262484 KB	Output is correct
71	Correct	209 ms	265956 KB	Output is correct
72	Correct	186 ms	265960 KB	Output is correct
73	Correct	209 ms	263880 KB	Output is correct
74	Correct	193 ms	263880 KB	Output is correct
75	Correct	159 ms	263432 KB	Output is correct
76	Correct	146 ms	265964 KB	Output is correct
77	Correct	106 ms	265964 KB	Output is correct
78	Correct	236 ms	261228 KB	Output is correct
79	Correct	206 ms	260664 KB	Output is correct
80	Correct	2493 ms	263584 KB	Output is correct
81	Correct	2406 ms	262808 KB	Output is correct
82	Correct	2446 ms	260260 KB	Output is correct
83	Correct	2463 ms	262920 KB	Output is correct
84	Correct	2539 ms	263580 KB	Output is correct
85	Correct	1996 ms	260716 KB	Output is correct
86	Correct	1839 ms	262944 KB	Output is correct
87	Correct	1999 ms	259836 KB	Output is correct
88	Correct	2709 ms	259836 KB	Output is correct
89	Correct	1766 ms	322212 KB	Output is correct
90	Correct	1639 ms	290960 KB	Output is correct
91	Correct	1706 ms	290960 KB	Output is correct
92	Correct	2143 ms	259836 KB	Output is correct
93	Correct	1943 ms	259836 KB	Output is correct
94	Correct	2509 ms	259836 KB	Output is correct
95	Correct	2453 ms	259836 KB	Output is correct
96	Correct	2343 ms	259836 KB	Output is correct
97	Correct	2039 ms	259836 KB	Output is correct
98	Correct	1876 ms	259836 KB	Output is correct
99	Correct	1766 ms	259836 KB	Output is correct
100	Correct	2849 ms	322208 KB	Output is correct
101	Correct	2916 ms	322208 KB	Output is correct
102	Correct	2669 ms	290976 KB	Output is correct
103	Correct	2646 ms	290936 KB	Output is correct
104	Correct	2356 ms	287488 KB	Output is correct
105	Correct	2599 ms	287488 KB	Output is correct
106	Correct	2549 ms	322208 KB	Output is correct
107	Correct	2643 ms	322208 KB	Output is correct
108	Correct	2559 ms	301380 KB	Output is correct
109	Correct	2723 ms	301380 KB	Output is correct
110	Correct	1873 ms	320940 KB	Output is correct
111	Correct	1953 ms	322216 KB	Output is correct
112	Correct	1329 ms	322208 KB	Output is correct
113	Correct	2386 ms	260276 KB	Output is correct
114	Correct	2466 ms	262740 KB	Output is correct

Submission #23709

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 56.0 / 56.0

Subtask #4 22.0 / 22.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
56.0 / 56.0

Subtask #4
22.0 / 22.0