oj.uz

답안 #825017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
825017 2023-08-14T13:29:21 Z MohamedAhmed04 Port Facility (JOI17_port_facility) C++14
100 / 100
 3899 ms 241072 KB 
#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<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 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 324 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 0 ms 324 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 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 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 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 1 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 1 ms 324 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 0 ms 324 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 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 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 3 ms 724 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 3 ms 728 KB Output is correct
28 Correct 5 ms 704 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 724 KB Output is correct
34 Correct 3 ms 724 KB Output is correct
35 Correct 2 ms 724 KB Output is correct
36 Correct 3 ms 596 KB Output is correct
37 Correct 3 ms 724 KB Output is correct
38 Correct 3 ms 724 KB Output is correct
39 Correct 2 ms 596 KB Output is correct
40 Correct 2 ms 724 KB Output is correct
41 Correct 3 ms 860 KB Output is correct
42 Correct 3 ms 852 KB Output is correct
43 Correct 3 ms 852 KB Output is correct
44 Correct 3 ms 852 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 324 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 0 ms 324 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 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 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 3 ms 724 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 3 ms 728 KB Output is correct
28 Correct 5 ms 704 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 724 KB Output is correct
34 Correct 3 ms 724 KB Output is correct
35 Correct 2 ms 724 KB Output is correct
36 Correct 3 ms 596 KB Output is correct
37 Correct 3 ms 724 KB Output is correct
38 Correct 3 ms 724 KB Output is correct
39 Correct 2 ms 596 KB Output is correct
40 Correct 2 ms 724 KB Output is correct
41 Correct 3 ms 860 KB Output is correct
42 Correct 3 ms 852 KB Output is correct
43 Correct 3 ms 852 KB Output is correct
44 Correct 3 ms 852 KB Output is correct
45 Correct 183 ms 18320 KB Output is correct
46 Correct 182 ms 19576 KB Output is correct
47 Correct 196 ms 17424 KB Output is correct
48 Correct 181 ms 19436 KB Output is correct
49 Correct 176 ms 17520 KB Output is correct
50 Correct 198 ms 16908 KB Output is correct
51 Correct 167 ms 17368 KB Output is correct
52 Correct 126 ms 18772 KB Output is correct
53 Correct 172 ms 18764 KB Output is correct
54 Correct 181 ms 23776 KB Output is correct
55 Correct 179 ms 19044 KB Output is correct
56 Correct 187 ms 18972 KB Output is correct
57 Correct 165 ms 16452 KB Output is correct
58 Correct 144 ms 18844 KB Output is correct
59 Correct 147 ms 18392 KB Output is correct
60 Correct 189 ms 17456 KB Output is correct
61 Correct 178 ms 17084 KB Output is correct
62 Correct 154 ms 14712 KB Output is correct
63 Correct 155 ms 14796 KB Output is correct
64 Correct 150 ms 14276 KB Output is correct
65 Correct 272 ms 23744 KB Output is correct
66 Correct 226 ms 23736 KB Output is correct
67 Correct 223 ms 21096 KB Output is correct
68 Correct 220 ms 21168 KB Output is correct
69 Correct 222 ms 21408 KB Output is correct
70 Correct 201 ms 21440 KB Output is correct
71 Correct 206 ms 25872 KB Output is correct
72 Correct 208 ms 25816 KB Output is correct
73 Correct 189 ms 23476 KB Output is correct
74 Correct 190 ms 23560 KB Output is correct
75 Correct 157 ms 21980 KB Output is correct
76 Correct 140 ms 25824 KB Output is correct
77 Correct 131 ms 23900 KB Output is correct
78 Correct 179 ms 19196 KB Output is correct
79 Correct 179 ms 18368 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 324 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 0 ms 324 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 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 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 3 ms 724 KB Output is correct
26 Correct 3 ms 724 KB Output is correct
27 Correct 3 ms 728 KB Output is correct
28 Correct 5 ms 704 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 724 KB Output is correct
34 Correct 3 ms 724 KB Output is correct
35 Correct 2 ms 724 KB Output is correct
36 Correct 3 ms 596 KB Output is correct
37 Correct 3 ms 724 KB Output is correct
38 Correct 3 ms 724 KB Output is correct
39 Correct 2 ms 596 KB Output is correct
40 Correct 2 ms 724 KB Output is correct
41 Correct 3 ms 860 KB Output is correct
42 Correct 3 ms 852 KB Output is correct
43 Correct 3 ms 852 KB Output is correct
44 Correct 3 ms 852 KB Output is correct
45 Correct 183 ms 18320 KB Output is correct
46 Correct 182 ms 19576 KB Output is correct
47 Correct 196 ms 17424 KB Output is correct
48 Correct 181 ms 19436 KB Output is correct
49 Correct 176 ms 17520 KB Output is correct
50 Correct 198 ms 16908 KB Output is correct
51 Correct 167 ms 17368 KB Output is correct
52 Correct 126 ms 18772 KB Output is correct
53 Correct 172 ms 18764 KB Output is correct
54 Correct 181 ms 23776 KB Output is correct
55 Correct 179 ms 19044 KB Output is correct
56 Correct 187 ms 18972 KB Output is correct
57 Correct 165 ms 16452 KB Output is correct
58 Correct 144 ms 18844 KB Output is correct
59 Correct 147 ms 18392 KB Output is correct
60 Correct 189 ms 17456 KB Output is correct
61 Correct 178 ms 17084 KB Output is correct
62 Correct 154 ms 14712 KB Output is correct
63 Correct 155 ms 14796 KB Output is correct
64 Correct 150 ms 14276 KB Output is correct
65 Correct 272 ms 23744 KB Output is correct
66 Correct 226 ms 23736 KB Output is correct
67 Correct 223 ms 21096 KB Output is correct
68 Correct 220 ms 21168 KB Output is correct
69 Correct 222 ms 21408 KB Output is correct
70 Correct 201 ms 21440 KB Output is correct
71 Correct 206 ms 25872 KB Output is correct
72 Correct 208 ms 25816 KB Output is correct
73 Correct 189 ms 23476 KB Output is correct
74 Correct 190 ms 23560 KB Output is correct
75 Correct 157 ms 21980 KB Output is correct
76 Correct 140 ms 25824 KB Output is correct
77 Correct 131 ms 23900 KB Output is correct
78 Correct 179 ms 19196 KB Output is correct
79 Correct 179 ms 18368 KB Output is correct
80 Correct 2357 ms 157396 KB Output is correct
81 Correct 2294 ms 156360 KB Output is correct
82 Correct 2304 ms 152500 KB Output is correct
83 Correct 2317 ms 156408 KB Output is correct
84 Correct 2343 ms 157640 KB Output is correct
85 Correct 2078 ms 134796 KB Output is correct
86 Correct 2189 ms 141404 KB Output is correct
87 Correct 1914 ms 170556 KB Output is correct
88 Correct 2686 ms 170620 KB Output is correct
89 Correct 2297 ms 217708 KB Output is correct
90 Correct 2193 ms 170780 KB Output is correct
91 Correct 2229 ms 170840 KB Output is correct
92 Correct 2017 ms 147096 KB Output is correct
93 Correct 1943 ms 170588 KB Output is correct
94 Correct 2135 ms 162280 KB Output is correct
95 Correct 2221 ms 154180 KB Output is correct
96 Correct 2338 ms 151980 KB Output is correct
97 Correct 2139 ms 147368 KB Output is correct
98 Correct 2219 ms 141660 KB Output is correct
99 Correct 2052 ms 127392 KB Output is correct
100 Correct 3715 ms 217696 KB Output is correct
101 Correct 3899 ms 217672 KB Output is correct
102 Correct 2596 ms 194128 KB Output is correct
103 Correct 2537 ms 193984 KB Output is correct
104 Correct 2662 ms 196616 KB Output is correct
105 Correct 2550 ms 196716 KB Output is correct
106 Correct 2594 ms 241072 KB Output is correct
107 Correct 2636 ms 241056 KB Output is correct
108 Correct 2579 ms 217676 KB Output is correct
109 Correct 2522 ms 217520 KB Output is correct
110 Correct 1946 ms 239196 KB Output is correct
111 Correct 2134 ms 240960 KB Output is correct
112 Correct 1637 ms 223428 KB Output is correct
113 Correct 2168 ms 152540 KB Output is correct
114 Correct 2262 ms 156388 KB Output is correct