답안 #825021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825021	2023-08-14T13:32:40 Z	MohamedAhmed04	Port Facility (JOI17_port_facility)	C++14	100 / 100	3401 ms	226488 KB

port_facility

#include <bits/stdc++.h>

using namespace std ;

const int mod = 1e9 + 7 ;

int Add(int x , int y)
{
	int z = x + y ;
	if(z >= mod)
		z -= mod ;
	return z ;
}

int Sub(int x , int y)
{
	int z = x - y ;
	if(z < 0)
		z += mod ;
	return z ;
}

int Mul(int x , int y)
{
	return (1ll * x * y) % mod ;
}

int powlog(int base , int power)
{
	if(power == 0)
		return 1 ;
	int x = powlog(base , power / 2) ;
	if(power & 1)
		x = Mul(x , base) ;
	return x ;
}

const int MAX = 2e6 + 10 ;

int arr[MAX] ;
int n ;

int L[MAX] , R[MAX] ;
int to[MAX] , back[MAX] ;
int id[MAX] ;

pair<int , int>tree[2][4 * MAX] ;

void build(int node , int l , int r)
{
	if(l == r)
	{
		tree[0][node].first = to[l] ;
		tree[1][node].first = back[l] ;
		tree[0][node].second = tree[1][node].second = id[l] ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid) ;
	build(node << 1 | 1 , mid+1 , r) ;
	tree[0][node] = max(tree[0][node << 1] , tree[0][node << 1 | 1]) ;
	tree[1][node] = min(tree[1][node << 1] , tree[1][node << 1 | 1]) ;
}

void update(int node , int l , int r , int idx , int val , bool t)
{
	if(l == r)
	{
		tree[t][node].first = val ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	if(idx <= mid)
		update(node << 1 , l , mid , idx , val , t) ;
	else
		update(node << 1 | 1 , mid+1 , r , idx , val , t) ;
	if(!t)
		tree[0][node] = max(tree[0][node << 1] , tree[0][node << 1 | 1]) ;
	else
		tree[1][node] = min(tree[1][node << 1] , tree[1][node << 1 | 1]) ;
}

pair<int , int>query(int node , int l , int r , int from , int to , bool t)
{
	if(from > r || to < l || from > to)
	{
		if(!t)
			return {-1e9 , -1e9} ;
		else
			return {1e9 , 1e9} ;
	}
	if(l >= from && r <= to)
		return tree[t][node] ;
	int mid = (l + r) >> 1 ;
	pair<int , int>a = query(node << 1 , l , mid , from , to , t) ;
	pair<int , int>b = query(node << 1 | 1 , mid+1 , r , from , to , t) ;
	if(!t)
		return max(a , b) ;
	else
		return min(a , b) ;
}

int vis[MAX] ;
vector< pair<int , int> >vp[2] ;

void dfs(int node , int col)
{
	vis[node] = 1 ;
	vp[col].emplace_back(L[node] , R[node]) ;
	update(1 , 1 , 2*n , L[node] , -1e9 , 0) ;
	update(1 , 1 , 2*n , R[node] , 1e9 , 1) ;
	bool ok = false ;
	while(!ok)
	{
		ok = true ;
		pair<int , int>p = query(1 , 1 , 2*n , L[node] , R[node] , 0) ;
		if(p.first > R[node])
			dfs(p.second , !col) , ok = false ;
		p = query(1 , 1 , 2*n , L[node] , R[node] , 1) ;
		if(p.first < L[node])
			dfs(p.second , !col) , ok = false ;
	}
}

bool check(bool t)
{
	sort(vp[t].begin() , vp[t].end()) ;
	set<int>s ;
	for(auto &p : vp[t])
	{
		auto it = s.lower_bound(p.second) ;
		if(it != s.begin())
		{
			it-- ;
			int x = *it ;
			if(p.first < x)
				return false ;
		}
		s.insert(p.second) ;
	}
	return true ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= 2*n ; ++i)
		to[i] = -1e9 , back[i] = 1e9 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>L[i]>>R[i] ;
		to[L[i]] = R[i] , back[R[i]] = L[i] ;
		id[L[i]] = id[R[i]] = i ;
	}
	build(1 , 1 , 2*n) ;
	int ans = 1 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(vis[i])
			continue ;
		dfs(i , 0) ;
		ans = Mul(ans , 2) ;
	}
	if((!check(0)) || (!check(1)))
		ans = 0 ;
	return cout<<ans<<"\n" , 0 ;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	4 ms	704 KB	Output is correct
26	Correct	4 ms	724 KB	Output is correct
27	Correct	4 ms	724 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Correct	3 ms	724 KB	Output is correct
30	Correct	3 ms	724 KB	Output is correct
31	Correct	3 ms	724 KB	Output is correct
32	Correct	3 ms	724 KB	Output is correct
33	Correct	3 ms	656 KB	Output is correct
34	Correct	3 ms	596 KB	Output is correct
35	Correct	3 ms	596 KB	Output is correct
36	Correct	4 ms	596 KB	Output is correct
37	Correct	3 ms	724 KB	Output is correct
38	Correct	3 ms	596 KB	Output is correct
39	Correct	2 ms	596 KB	Output is correct
40	Correct	2 ms	596 KB	Output is correct
41	Correct	3 ms	724 KB	Output is correct
42	Correct	3 ms	724 KB	Output is correct
43	Correct	2 ms	724 KB	Output is correct
44	Correct	2 ms	724 KB	Output is correct

Subtask #3
56.0 / 56.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	4 ms	704 KB	Output is correct
26	Correct	4 ms	724 KB	Output is correct
27	Correct	4 ms	724 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Correct	3 ms	724 KB	Output is correct
30	Correct	3 ms	724 KB	Output is correct
31	Correct	3 ms	724 KB	Output is correct
32	Correct	3 ms	724 KB	Output is correct
33	Correct	3 ms	656 KB	Output is correct
34	Correct	3 ms	596 KB	Output is correct
35	Correct	3 ms	596 KB	Output is correct
36	Correct	4 ms	596 KB	Output is correct
37	Correct	3 ms	724 KB	Output is correct
38	Correct	3 ms	596 KB	Output is correct
39	Correct	2 ms	596 KB	Output is correct
40	Correct	2 ms	596 KB	Output is correct
41	Correct	3 ms	724 KB	Output is correct
42	Correct	3 ms	724 KB	Output is correct
43	Correct	2 ms	724 KB	Output is correct
44	Correct	2 ms	724 KB	Output is correct
45	Correct	190 ms	16992 KB	Output is correct
46	Correct	177 ms	18280 KB	Output is correct
47	Correct	169 ms	16152 KB	Output is correct
48	Correct	186 ms	18276 KB	Output is correct
49	Correct	168 ms	16256 KB	Output is correct
50	Correct	166 ms	15740 KB	Output is correct
51	Correct	157 ms	16052 KB	Output is correct
52	Correct	126 ms	17564 KB	Output is correct
53	Correct	159 ms	17496 KB	Output is correct
54	Correct	198 ms	22592 KB	Output is correct
55	Correct	174 ms	17816 KB	Output is correct
56	Correct	180 ms	17732 KB	Output is correct
57	Correct	143 ms	15208 KB	Output is correct
58	Correct	125 ms	17536 KB	Output is correct
59	Correct	151 ms	17192 KB	Output is correct
60	Correct	167 ms	16280 KB	Output is correct
61	Correct	175 ms	15856 KB	Output is correct
62	Correct	142 ms	13508 KB	Output is correct
63	Correct	166 ms	13588 KB	Output is correct
64	Correct	152 ms	13008 KB	Output is correct
65	Correct	220 ms	22616 KB	Output is correct
66	Correct	207 ms	22508 KB	Output is correct
67	Correct	194 ms	19940 KB	Output is correct
68	Correct	205 ms	20008 KB	Output is correct
69	Correct	211 ms	20168 KB	Output is correct
70	Correct	183 ms	20092 KB	Output is correct
71	Correct	196 ms	24568 KB	Output is correct
72	Correct	233 ms	24572 KB	Output is correct
73	Correct	189 ms	22248 KB	Output is correct
74	Correct	186 ms	22176 KB	Output is correct
75	Correct	138 ms	20752 KB	Output is correct
76	Correct	154 ms	24560 KB	Output is correct
77	Correct	140 ms	22720 KB	Output is correct
78	Correct	186 ms	17984 KB	Output is correct
79	Correct	229 ms	17088 KB	Output is correct

Subtask #4
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	4 ms	704 KB	Output is correct
26	Correct	4 ms	724 KB	Output is correct
27	Correct	4 ms	724 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Correct	3 ms	724 KB	Output is correct
30	Correct	3 ms	724 KB	Output is correct
31	Correct	3 ms	724 KB	Output is correct
32	Correct	3 ms	724 KB	Output is correct
33	Correct	3 ms	656 KB	Output is correct
34	Correct	3 ms	596 KB	Output is correct
35	Correct	3 ms	596 KB	Output is correct
36	Correct	4 ms	596 KB	Output is correct
37	Correct	3 ms	724 KB	Output is correct
38	Correct	3 ms	596 KB	Output is correct
39	Correct	2 ms	596 KB	Output is correct
40	Correct	2 ms	596 KB	Output is correct
41	Correct	3 ms	724 KB	Output is correct
42	Correct	3 ms	724 KB	Output is correct
43	Correct	2 ms	724 KB	Output is correct
44	Correct	2 ms	724 KB	Output is correct
45	Correct	190 ms	16992 KB	Output is correct
46	Correct	177 ms	18280 KB	Output is correct
47	Correct	169 ms	16152 KB	Output is correct
48	Correct	186 ms	18276 KB	Output is correct
49	Correct	168 ms	16256 KB	Output is correct
50	Correct	166 ms	15740 KB	Output is correct
51	Correct	157 ms	16052 KB	Output is correct
52	Correct	126 ms	17564 KB	Output is correct
53	Correct	159 ms	17496 KB	Output is correct
54	Correct	198 ms	22592 KB	Output is correct
55	Correct	174 ms	17816 KB	Output is correct
56	Correct	180 ms	17732 KB	Output is correct
57	Correct	143 ms	15208 KB	Output is correct
58	Correct	125 ms	17536 KB	Output is correct
59	Correct	151 ms	17192 KB	Output is correct
60	Correct	167 ms	16280 KB	Output is correct
61	Correct	175 ms	15856 KB	Output is correct
62	Correct	142 ms	13508 KB	Output is correct
63	Correct	166 ms	13588 KB	Output is correct
64	Correct	152 ms	13008 KB	Output is correct
65	Correct	220 ms	22616 KB	Output is correct
66	Correct	207 ms	22508 KB	Output is correct
67	Correct	194 ms	19940 KB	Output is correct
68	Correct	205 ms	20008 KB	Output is correct
69	Correct	211 ms	20168 KB	Output is correct
70	Correct	183 ms	20092 KB	Output is correct
71	Correct	196 ms	24568 KB	Output is correct
72	Correct	233 ms	24572 KB	Output is correct
73	Correct	189 ms	22248 KB	Output is correct
74	Correct	186 ms	22176 KB	Output is correct
75	Correct	138 ms	20752 KB	Output is correct
76	Correct	154 ms	24560 KB	Output is correct
77	Correct	140 ms	22720 KB	Output is correct
78	Correct	186 ms	17984 KB	Output is correct
79	Correct	229 ms	17088 KB	Output is correct
80	Correct	2179 ms	142900 KB	Output is correct
81	Correct	2346 ms	141816 KB	Output is correct
82	Correct	2220 ms	138028 KB	Output is correct
83	Correct	2248 ms	141904 KB	Output is correct
84	Correct	2230 ms	142860 KB	Output is correct
85	Correct	2069 ms	120176 KB	Output is correct
86	Correct	2130 ms	126776 KB	Output is correct
87	Correct	1862 ms	155912 KB	Output is correct
88	Correct	2490 ms	155924 KB	Output is correct
89	Correct	2165 ms	203100 KB	Output is correct
90	Correct	2114 ms	156196 KB	Output is correct
91	Correct	2289 ms	156168 KB	Output is correct
92	Correct	1931 ms	132600 KB	Output is correct
93	Correct	1854 ms	155956 KB	Output is correct
94	Correct	2150 ms	147708 KB	Output is correct
95	Correct	2151 ms	139532 KB	Output is correct
96	Correct	2103 ms	137468 KB	Output is correct
97	Correct	2047 ms	132700 KB	Output is correct
98	Correct	2058 ms	127052 KB	Output is correct
99	Correct	1876 ms	112980 KB	Output is correct
100	Correct	3401 ms	203220 KB	Output is correct
101	Correct	3318 ms	203212 KB	Output is correct
102	Correct	2536 ms	179556 KB	Output is correct
103	Correct	2381 ms	179492 KB	Output is correct
104	Correct	2401 ms	182120 KB	Output is correct
105	Correct	2394 ms	182076 KB	Output is correct
106	Correct	2490 ms	226376 KB	Output is correct
107	Correct	2497 ms	226376 KB	Output is correct
108	Correct	2417 ms	203004 KB	Output is correct
109	Correct	2469 ms	202920 KB	Output is correct
110	Correct	1877 ms	224480 KB	Output is correct
111	Correct	1957 ms	226488 KB	Output is correct
112	Correct	1527 ms	209040 KB	Output is correct
113	Correct	2237 ms	137932 KB	Output is correct
114	Correct	2160 ms	141756 KB	Output is correct

답안 #825021

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