답안 #825031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825031	2023-08-14T13:44:37 Z	MohamedAhmed04	Port Facility (JOI17_port_facility)	C++17	100 / 100	2578 ms	156064 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(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[t][node].first = val ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx , val , t) ;
	update(node << 1 | 1 , mid+1 , r , idx , val , t) ;
	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]) ;
}

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

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

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

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 ;
		bfs(i) ;
		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	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 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	1 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	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 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	1 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	2 ms	596 KB	Output is correct
26	Correct	2 ms	596 KB	Output is correct
27	Correct	2 ms	596 KB	Output is correct
28	Correct	2 ms	596 KB	Output is correct
29	Correct	3 ms	640 KB	Output is correct
30	Correct	2 ms	596 KB	Output is correct
31	Correct	2 ms	596 KB	Output is correct
32	Correct	2 ms	596 KB	Output is correct
33	Correct	2 ms	632 KB	Output is correct
34	Correct	2 ms	596 KB	Output is correct
35	Correct	2 ms	596 KB	Output is correct
36	Correct	3 ms	596 KB	Output is correct
37	Correct	2 ms	608 KB	Output is correct
38	Correct	2 ms	596 KB	Output is correct
39	Correct	3 ms	596 KB	Output is correct
40	Correct	2 ms	596 KB	Output is correct
41	Correct	2 ms	596 KB	Output is correct
42	Correct	2 ms	596 KB	Output is correct
43	Correct	2 ms	596 KB	Output is correct
44	Correct	2 ms	596 KB	Output is correct

Subtask #3
56.0 / 56.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 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	1 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	2 ms	596 KB	Output is correct
26	Correct	2 ms	596 KB	Output is correct
27	Correct	2 ms	596 KB	Output is correct
28	Correct	2 ms	596 KB	Output is correct
29	Correct	3 ms	640 KB	Output is correct
30	Correct	2 ms	596 KB	Output is correct
31	Correct	2 ms	596 KB	Output is correct
32	Correct	2 ms	596 KB	Output is correct
33	Correct	2 ms	632 KB	Output is correct
34	Correct	2 ms	596 KB	Output is correct
35	Correct	2 ms	596 KB	Output is correct
36	Correct	3 ms	596 KB	Output is correct
37	Correct	2 ms	608 KB	Output is correct
38	Correct	2 ms	596 KB	Output is correct
39	Correct	3 ms	596 KB	Output is correct
40	Correct	2 ms	596 KB	Output is correct
41	Correct	2 ms	596 KB	Output is correct
42	Correct	2 ms	596 KB	Output is correct
43	Correct	2 ms	596 KB	Output is correct
44	Correct	2 ms	596 KB	Output is correct
45	Correct	158 ms	16068 KB	Output is correct
46	Correct	139 ms	15988 KB	Output is correct
47	Correct	131 ms	16112 KB	Output is correct
48	Correct	151 ms	16068 KB	Output is correct
49	Correct	140 ms	16124 KB	Output is correct
50	Correct	116 ms	13788 KB	Output is correct
51	Correct	127 ms	14344 KB	Output is correct
52	Correct	128 ms	17596 KB	Output is correct
53	Correct	139 ms	17532 KB	Output is correct
54	Correct	108 ms	14000 KB	Output is correct
55	Correct	125 ms	13820 KB	Output is correct
56	Correct	124 ms	13924 KB	Output is correct
57	Correct	114 ms	15576 KB	Output is correct
58	Correct	162 ms	17576 KB	Output is correct
59	Correct	131 ms	17600 KB	Output is correct
60	Correct	144 ms	16660 KB	Output is correct
61	Correct	144 ms	16212 KB	Output is correct
62	Correct	100 ms	13792 KB	Output is correct
63	Correct	115 ms	14016 KB	Output is correct
64	Correct	148 ms	13960 KB	Output is correct
65	Correct	158 ms	13864 KB	Output is correct
66	Correct	143 ms	14088 KB	Output is correct
67	Correct	127 ms	15668 KB	Output is correct
68	Correct	128 ms	15612 KB	Output is correct
69	Correct	132 ms	16432 KB	Output is correct
70	Correct	124 ms	16364 KB	Output is correct
71	Correct	128 ms	15640 KB	Output is correct
72	Correct	135 ms	15716 KB	Output is correct
73	Correct	130 ms	16400 KB	Output is correct
74	Correct	194 ms	16412 KB	Output is correct
75	Correct	145 ms	15564 KB	Output is correct
76	Correct	118 ms	15648 KB	Output is correct
77	Correct	104 ms	15648 KB	Output is correct
78	Correct	128 ms	16008 KB	Output is correct
79	Correct	157 ms	16056 KB	Output is correct

Subtask #4
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 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	1 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	2 ms	596 KB	Output is correct
26	Correct	2 ms	596 KB	Output is correct
27	Correct	2 ms	596 KB	Output is correct
28	Correct	2 ms	596 KB	Output is correct
29	Correct	3 ms	640 KB	Output is correct
30	Correct	2 ms	596 KB	Output is correct
31	Correct	2 ms	596 KB	Output is correct
32	Correct	2 ms	596 KB	Output is correct
33	Correct	2 ms	632 KB	Output is correct
34	Correct	2 ms	596 KB	Output is correct
35	Correct	2 ms	596 KB	Output is correct
36	Correct	3 ms	596 KB	Output is correct
37	Correct	2 ms	608 KB	Output is correct
38	Correct	2 ms	596 KB	Output is correct
39	Correct	3 ms	596 KB	Output is correct
40	Correct	2 ms	596 KB	Output is correct
41	Correct	2 ms	596 KB	Output is correct
42	Correct	2 ms	596 KB	Output is correct
43	Correct	2 ms	596 KB	Output is correct
44	Correct	2 ms	596 KB	Output is correct
45	Correct	158 ms	16068 KB	Output is correct
46	Correct	139 ms	15988 KB	Output is correct
47	Correct	131 ms	16112 KB	Output is correct
48	Correct	151 ms	16068 KB	Output is correct
49	Correct	140 ms	16124 KB	Output is correct
50	Correct	116 ms	13788 KB	Output is correct
51	Correct	127 ms	14344 KB	Output is correct
52	Correct	128 ms	17596 KB	Output is correct
53	Correct	139 ms	17532 KB	Output is correct
54	Correct	108 ms	14000 KB	Output is correct
55	Correct	125 ms	13820 KB	Output is correct
56	Correct	124 ms	13924 KB	Output is correct
57	Correct	114 ms	15576 KB	Output is correct
58	Correct	162 ms	17576 KB	Output is correct
59	Correct	131 ms	17600 KB	Output is correct
60	Correct	144 ms	16660 KB	Output is correct
61	Correct	144 ms	16212 KB	Output is correct
62	Correct	100 ms	13792 KB	Output is correct
63	Correct	115 ms	14016 KB	Output is correct
64	Correct	148 ms	13960 KB	Output is correct
65	Correct	158 ms	13864 KB	Output is correct
66	Correct	143 ms	14088 KB	Output is correct
67	Correct	127 ms	15668 KB	Output is correct
68	Correct	128 ms	15612 KB	Output is correct
69	Correct	132 ms	16432 KB	Output is correct
70	Correct	124 ms	16364 KB	Output is correct
71	Correct	128 ms	15640 KB	Output is correct
72	Correct	135 ms	15716 KB	Output is correct
73	Correct	130 ms	16400 KB	Output is correct
74	Correct	194 ms	16412 KB	Output is correct
75	Correct	145 ms	15564 KB	Output is correct
76	Correct	118 ms	15648 KB	Output is correct
77	Correct	104 ms	15648 KB	Output is correct
78	Correct	128 ms	16008 KB	Output is correct
79	Correct	157 ms	16056 KB	Output is correct
80	Correct	2083 ms	141024 KB	Output is correct
81	Correct	1914 ms	141028 KB	Output is correct
82	Correct	1923 ms	140948 KB	Output is correct
83	Correct	1891 ms	141104 KB	Output is correct
84	Correct	1900 ms	140948 KB	Output is correct
85	Correct	1878 ms	122440 KB	Output is correct
86	Correct	1912 ms	125832 KB	Output is correct
87	Correct	1711 ms	156064 KB	Output is correct
88	Correct	2094 ms	156012 KB	Output is correct
89	Correct	1610 ms	117600 KB	Output is correct
90	Correct	1743 ms	115552 KB	Output is correct
91	Correct	2269 ms	115548 KB	Output is correct
92	Correct	1691 ms	136436 KB	Output is correct
93	Correct	1795 ms	156012 KB	Output is correct
94	Correct	2109 ms	151608 KB	Output is correct
95	Correct	2404 ms	143532 KB	Output is correct
96	Correct	2398 ms	141280 KB	Output is correct
97	Correct	1806 ms	123700 KB	Output is correct
98	Correct	1918 ms	125108 KB	Output is correct
99	Correct	1808 ms	116672 KB	Output is correct
100	Correct	2578 ms	119552 KB	Output is correct
101	Correct	2465 ms	123872 KB	Output is correct
102	Correct	1879 ms	136436 KB	Output is correct
103	Correct	1789 ms	136524 KB	Output is correct
104	Correct	1737 ms	144320 KB	Output is correct
105	Correct	1807 ms	144416 KB	Output is correct
106	Correct	1894 ms	136500 KB	Output is correct
107	Correct	1704 ms	136564 KB	Output is correct
108	Correct	1901 ms	144408 KB	Output is correct
109	Correct	1856 ms	144284 KB	Output is correct
110	Correct	1509 ms	136392 KB	Output is correct
111	Correct	1578 ms	136512 KB	Output is correct
112	Correct	1569 ms	136448 KB	Output is correct
113	Correct	1813 ms	141096 KB	Output is correct
114	Correct	1803 ms	141032 KB	Output is correct

답안 #825031

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