oj.uz

Submission #87087

# Submission time Handle Problem Language Result Execution time Memory
87087 2018-11-29T12:57:20 Z JustInCase Port Facility (JOI17_port_facility) C++17
100 / 100
 5400 ms 638972 KB 
#include <bits/stdc++.h>

const int32_t MAX_N = 1e6;
const int32_t INF = 2e9;
const int32_t MOD = 1e9 + 7;

class SegmentTree {
private:
	bool isMax;
	int32_t treeSize;
	int32_t data[8 * MAX_N + 5];

	void Update(int32_t node, int32_t low, int32_t high, int32_t qInd, int32_t qVal) {
		if(low > qInd || high < qInd) {
			return;
		}
		else if(low == qInd && high == qInd) {
			data[node] = qVal;
			return;
		}

		int32_t mid = (low + high) / 2;
		Update(2 * node, low, mid, qInd, qVal);
		Update(2 * node + 1, mid + 1, high, qInd, qVal);

		if(isMax) {
			data[node] = std::max(data[2 * node], data[2 * node + 1]);
		}
		else {
			data[node] = std::min(data[2 * node], data[2 * node + 1]);
		}
	}

	int32_t Query(int32_t node, int32_t low, int32_t high, int32_t qLow, int32_t qHigh) {
		if(low > qHigh || high < qLow) {
			if(isMax) {
				return -1;
			}
			else {
				return INF;
			}
		}
		else if(low >= qLow && high <= qHigh) {
			return data[node];
		}

		int32_t mid = (low + high) / 2;
		
		if(isMax) {
			return std::max(Query(2 * node, low, mid, qLow, qHigh), Query(2 * node + 1, mid + 1, high, qLow, qHigh));
		}
		else {
			return std::min(Query(2 * node, low, mid, qLow, qHigh), Query(2 * node + 1, mid + 1, high, qLow, qHigh));
		}
	}

public:
	void Init(int32_t _treeSize, bool _isMax) {
		treeSize = _treeSize;
		isMax = _isMax;
	}

	void Update(int32_t ind, int32_t val) {
		Update(1, 1, treeSize, ind, val);
	}

	int32_t Query(int32_t low, int32_t high) {
		return Query(1, 1, treeSize, low, high);
	}
};

int32_t comps[MAX_N + 5], indOf[2 * MAX_N + 5];
std::pair< int32_t, int32_t > a[MAX_N + 5];
SegmentTree segTreeStarts, segTreeEnds;

void Dfs(int32_t ind, int32_t currComp) {
	comps[ind] = currComp;

	segTreeStarts.Update(a[ind].first, -1);
	segTreeEnds.Update(a[ind].second, INF);
	
	while(1) {
		int32_t aux = segTreeStarts.Query(a[ind].first + 1, a[ind].second - 1);
		
		if(aux > a[ind].second) {
			Dfs(indOf[aux], (currComp ^ 1));
		}
		else {
			break;
		}
	}

	while(1) {
		int32_t aux = segTreeEnds.Query(a[ind].first + 1, a[ind].second - 1);
	
		if(aux < a[ind].first) {
			Dfs(indOf[aux], (currComp ^ 1));
		}
		else {
			break;
		}
	}
}

bool Check(int32_t n) {
	std::vector< int32_t > side1, side2;
	for(int32_t i = 0; i < n; i++) {
		if(comps[i] == 0) {
			side1.push_back(i);
		}
		else {
			side2.push_back(i);
		}
	}

	std::stack< int32_t > st;
	for(auto &x : side1) {
		while(!st.empty() && st.top() < a[x].first) {
			st.pop();
		}

		if(!st.empty() && st.top() < a[x].second) {
			return false;
		}
		else {
			st.push(a[x].second);
		}
	}

	while(!st.empty()) {
		st.pop();
	}

	for(auto &x : side2) {
		while(!st.empty() && st.top() < a[x].first) {
			st.pop();
		}

		if(!st.empty() && st.top() < a[x].second) {
			return false;
		}
		else {
			st.push(a[x].second);
		}
	}	

	return true;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n;
	std::cin >> n;

	segTreeStarts.Init(2 * n, 1);
	segTreeEnds.Init(2 * n, 0);

	for(int32_t i = 0; i < n; i++) {
		std::cin >> a[i].first >> a[i].second;
	
		segTreeStarts.Update(a[i].first, a[i].second);
		segTreeStarts.Update(a[i].second, -1);

		segTreeEnds.Update(a[i].second, a[i].first);
		segTreeEnds.Update(a[i].first, INF);
	}

	std::sort(a, a + n);
	for(int32_t i = 0; i < n; i++) {
		indOf[a[i].first] = i;
		indOf[a[i].second] = i;
	}

	int32_t cntComps = 0;
	memset(comps, -1, sizeof(comps));
	for(int32_t i = 0; i < n; i++) {
		if(comps[i] == -1) {
			cntComps++;
			Dfs(i, 0);
		}
	}

	if(Check(n)) {
		int32_t ans = 1;
		for(int32_t i = 0; i < cntComps; i++) {
			ans = ((int64_t) 2 * ans) % MOD;
		}

		std::cout << ans << '\n';
	}
	else {
		std::cout << 0 << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4472 KB Output is correct
3 Correct 6 ms 4504 KB Output is correct
4 Correct 10 ms 4728 KB Output is correct
5 Correct 6 ms 4728 KB Output is correct
6 Correct 5 ms 4728 KB Output is correct
7 Correct 5 ms 4728 KB Output is correct
8 Correct 5 ms 4728 KB Output is correct
9 Correct 6 ms 4728 KB Output is correct
10 Correct 6 ms 4728 KB Output is correct
11 Correct 5 ms 4728 KB Output is correct
12 Correct 6 ms 4728 KB Output is correct
13 Correct 5 ms 4728 KB Output is correct
14 Correct 7 ms 4728 KB Output is correct
15 Correct 7 ms 4728 KB Output is correct
16 Correct 6 ms 4728 KB Output is correct
17 Correct 5 ms 4792 KB Output is correct
18 Correct 5 ms 4840 KB Output is correct
19 Correct 5 ms 4840 KB Output is correct
20 Correct 6 ms 4916 KB Output is correct
21 Correct 5 ms 4916 KB Output is correct
22 Correct 5 ms 4916 KB Output is correct
23 Correct 5 ms 4916 KB Output is correct
24 Correct 6 ms 4916 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4472 KB Output is correct
3 Correct 6 ms 4504 KB Output is correct
4 Correct 10 ms 4728 KB Output is correct
5 Correct 6 ms 4728 KB Output is correct
6 Correct 5 ms 4728 KB Output is correct
7 Correct 5 ms 4728 KB Output is correct
8 Correct 5 ms 4728 KB Output is correct
9 Correct 6 ms 4728 KB Output is correct
10 Correct 6 ms 4728 KB Output is correct
11 Correct 5 ms 4728 KB Output is correct
12 Correct 6 ms 4728 KB Output is correct
13 Correct 5 ms 4728 KB Output is correct
14 Correct 7 ms 4728 KB Output is correct
15 Correct 7 ms 4728 KB Output is correct
16 Correct 6 ms 4728 KB Output is correct
17 Correct 5 ms 4792 KB Output is correct
18 Correct 5 ms 4840 KB Output is correct
19 Correct 5 ms 4840 KB Output is correct
20 Correct 6 ms 4916 KB Output is correct
21 Correct 5 ms 4916 KB Output is correct
22 Correct 5 ms 4916 KB Output is correct
23 Correct 5 ms 4916 KB Output is correct
24 Correct 6 ms 4916 KB Output is correct
25 Correct 9 ms 5144 KB Output is correct
26 Correct 11 ms 5144 KB Output is correct
27 Correct 10 ms 5296 KB Output is correct
28 Correct 9 ms 5296 KB Output is correct
29 Correct 9 ms 5296 KB Output is correct
30 Correct 10 ms 5296 KB Output is correct
31 Correct 10 ms 5296 KB Output is correct
32 Correct 9 ms 5300 KB Output is correct
33 Correct 9 ms 5320 KB Output is correct
34 Correct 10 ms 5356 KB Output is correct
35 Correct 9 ms 5356 KB Output is correct
36 Correct 9 ms 5356 KB Output is correct
37 Correct 9 ms 5544 KB Output is correct
38 Correct 9 ms 5544 KB Output is correct
39 Correct 9 ms 5544 KB Output is correct
40 Correct 8 ms 5544 KB Output is correct
41 Correct 12 ms 5624 KB Output is correct
42 Correct 9 ms 5644 KB Output is correct
43 Correct 9 ms 5664 KB Output is correct
44 Correct 9 ms 5684 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4472 KB Output is correct
3 Correct 6 ms 4504 KB Output is correct
4 Correct 10 ms 4728 KB Output is correct
5 Correct 6 ms 4728 KB Output is correct
6 Correct 5 ms 4728 KB Output is correct
7 Correct 5 ms 4728 KB Output is correct
8 Correct 5 ms 4728 KB Output is correct
9 Correct 6 ms 4728 KB Output is correct
10 Correct 6 ms 4728 KB Output is correct
11 Correct 5 ms 4728 KB Output is correct
12 Correct 6 ms 4728 KB Output is correct
13 Correct 5 ms 4728 KB Output is correct
14 Correct 7 ms 4728 KB Output is correct
15 Correct 7 ms 4728 KB Output is correct
16 Correct 6 ms 4728 KB Output is correct
17 Correct 5 ms 4792 KB Output is correct
18 Correct 5 ms 4840 KB Output is correct
19 Correct 5 ms 4840 KB Output is correct
20 Correct 6 ms 4916 KB Output is correct
21 Correct 5 ms 4916 KB Output is correct
22 Correct 5 ms 4916 KB Output is correct
23 Correct 5 ms 4916 KB Output is correct
24 Correct 6 ms 4916 KB Output is correct
25 Correct 9 ms 5144 KB Output is correct
26 Correct 11 ms 5144 KB Output is correct
27 Correct 10 ms 5296 KB Output is correct
28 Correct 9 ms 5296 KB Output is correct
29 Correct 9 ms 5296 KB Output is correct
30 Correct 10 ms 5296 KB Output is correct
31 Correct 10 ms 5296 KB Output is correct
32 Correct 9 ms 5300 KB Output is correct
33 Correct 9 ms 5320 KB Output is correct
34 Correct 10 ms 5356 KB Output is correct
35 Correct 9 ms 5356 KB Output is correct
36 Correct 9 ms 5356 KB Output is correct
37 Correct 9 ms 5544 KB Output is correct
38 Correct 9 ms 5544 KB Output is correct
39 Correct 9 ms 5544 KB Output is correct
40 Correct 8 ms 5544 KB Output is correct
41 Correct 12 ms 5624 KB Output is correct
42 Correct 9 ms 5644 KB Output is correct
43 Correct 9 ms 5664 KB Output is correct
44 Correct 9 ms 5684 KB Output is correct
45 Correct 285 ms 14188 KB Output is correct
46 Correct 295 ms 16824 KB Output is correct
47 Correct 287 ms 16824 KB Output is correct
48 Correct 294 ms 19336 KB Output is correct
49 Correct 287 ms 19336 KB Output is correct
50 Correct 263 ms 21472 KB Output is correct
51 Correct 260 ms 22736 KB Output is correct
52 Correct 217 ms 22736 KB Output is correct
53 Correct 257 ms 23232 KB Output is correct
54 Correct 266 ms 33688 KB Output is correct
55 Correct 258 ms 33688 KB Output is correct
56 Correct 272 ms 33688 KB Output is correct
57 Correct 218 ms 33688 KB Output is correct
58 Correct 217 ms 33688 KB Output is correct
59 Correct 229 ms 33688 KB Output is correct
60 Correct 247 ms 33688 KB Output is correct
61 Correct 255 ms 33688 KB Output is correct
62 Correct 228 ms 34632 KB Output is correct
63 Correct 238 ms 35860 KB Output is correct
64 Correct 255 ms 36960 KB Output is correct
65 Correct 327 ms 47664 KB Output is correct
66 Correct 330 ms 48684 KB Output is correct
67 Correct 280 ms 48684 KB Output is correct
68 Correct 276 ms 48684 KB Output is correct
69 Correct 280 ms 48684 KB Output is correct
70 Correct 290 ms 48932 KB Output is correct
71 Correct 301 ms 55188 KB Output is correct
72 Correct 314 ms 56448 KB Output is correct
73 Correct 283 ms 56448 KB Output is correct
74 Correct 275 ms 56448 KB Output is correct
75 Correct 249 ms 60228 KB Output is correct
76 Correct 241 ms 61488 KB Output is correct
77 Correct 254 ms 62788 KB Output is correct
78 Correct 258 ms 62788 KB Output is correct
79 Correct 284 ms 62788 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4472 KB Output is correct
3 Correct 6 ms 4504 KB Output is correct
4 Correct 10 ms 4728 KB Output is correct
5 Correct 6 ms 4728 KB Output is correct
6 Correct 5 ms 4728 KB Output is correct
7 Correct 5 ms 4728 KB Output is correct
8 Correct 5 ms 4728 KB Output is correct
9 Correct 6 ms 4728 KB Output is correct
10 Correct 6 ms 4728 KB Output is correct
11 Correct 5 ms 4728 KB Output is correct
12 Correct 6 ms 4728 KB Output is correct
13 Correct 5 ms 4728 KB Output is correct
14 Correct 7 ms 4728 KB Output is correct
15 Correct 7 ms 4728 KB Output is correct
16 Correct 6 ms 4728 KB Output is correct
17 Correct 5 ms 4792 KB Output is correct
18 Correct 5 ms 4840 KB Output is correct
19 Correct 5 ms 4840 KB Output is correct
20 Correct 6 ms 4916 KB Output is correct
21 Correct 5 ms 4916 KB Output is correct
22 Correct 5 ms 4916 KB Output is correct
23 Correct 5 ms 4916 KB Output is correct
24 Correct 6 ms 4916 KB Output is correct
25 Correct 9 ms 5144 KB Output is correct
26 Correct 11 ms 5144 KB Output is correct
27 Correct 10 ms 5296 KB Output is correct
28 Correct 9 ms 5296 KB Output is correct
29 Correct 9 ms 5296 KB Output is correct
30 Correct 10 ms 5296 KB Output is correct
31 Correct 10 ms 5296 KB Output is correct
32 Correct 9 ms 5300 KB Output is correct
33 Correct 9 ms 5320 KB Output is correct
34 Correct 10 ms 5356 KB Output is correct
35 Correct 9 ms 5356 KB Output is correct
36 Correct 9 ms 5356 KB Output is correct
37 Correct 9 ms 5544 KB Output is correct
38 Correct 9 ms 5544 KB Output is correct
39 Correct 9 ms 5544 KB Output is correct
40 Correct 8 ms 5544 KB Output is correct
41 Correct 12 ms 5624 KB Output is correct
42 Correct 9 ms 5644 KB Output is correct
43 Correct 9 ms 5664 KB Output is correct
44 Correct 9 ms 5684 KB Output is correct
45 Correct 285 ms 14188 KB Output is correct
46 Correct 295 ms 16824 KB Output is correct
47 Correct 287 ms 16824 KB Output is correct
48 Correct 294 ms 19336 KB Output is correct
49 Correct 287 ms 19336 KB Output is correct
50 Correct 263 ms 21472 KB Output is correct
51 Correct 260 ms 22736 KB Output is correct
52 Correct 217 ms 22736 KB Output is correct
53 Correct 257 ms 23232 KB Output is correct
54 Correct 266 ms 33688 KB Output is correct
55 Correct 258 ms 33688 KB Output is correct
56 Correct 272 ms 33688 KB Output is correct
57 Correct 218 ms 33688 KB Output is correct
58 Correct 217 ms 33688 KB Output is correct
59 Correct 229 ms 33688 KB Output is correct
60 Correct 247 ms 33688 KB Output is correct
61 Correct 255 ms 33688 KB Output is correct
62 Correct 228 ms 34632 KB Output is correct
63 Correct 238 ms 35860 KB Output is correct
64 Correct 255 ms 36960 KB Output is correct
65 Correct 327 ms 47664 KB Output is correct
66 Correct 330 ms 48684 KB Output is correct
67 Correct 280 ms 48684 KB Output is correct
68 Correct 276 ms 48684 KB Output is correct
69 Correct 280 ms 48684 KB Output is correct
70 Correct 290 ms 48932 KB Output is correct
71 Correct 301 ms 55188 KB Output is correct
72 Correct 314 ms 56448 KB Output is correct
73 Correct 283 ms 56448 KB Output is correct
74 Correct 275 ms 56448 KB Output is correct
75 Correct 249 ms 60228 KB Output is correct
76 Correct 241 ms 61488 KB Output is correct
77 Correct 254 ms 62788 KB Output is correct
78 Correct 258 ms 62788 KB Output is correct
79 Correct 284 ms 62788 KB Output is correct
80 Correct 3612 ms 124424 KB Output is correct
81 Correct 3557 ms 137700 KB Output is correct
82 Correct 3602 ms 149196 KB Output is correct
83 Correct 3616 ms 166960 KB Output is correct
84 Correct 3514 ms 182512 KB Output is correct
85 Correct 3819 ms 193024 KB Output is correct
86 Correct 3709 ms 210748 KB Output is correct
87 Correct 2715 ms 218924 KB Output is correct
88 Correct 3423 ms 237360 KB Output is correct
89 Correct 3731 ms 340024 KB Output is correct
90 Correct 3695 ms 340024 KB Output is correct
91 Correct 3672 ms 340024 KB Output is correct
92 Correct 2840 ms 340024 KB Output is correct
93 Correct 2866 ms 340024 KB Output is correct
94 Correct 3280 ms 340024 KB Output is correct
95 Correct 3394 ms 340024 KB Output is correct
96 Correct 3405 ms 348860 KB Output is correct
97 Correct 3234 ms 363788 KB Output is correct
98 Correct 3355 ms 375480 KB Output is correct
99 Correct 3497 ms 390152 KB Output is correct
100 Correct 5400 ms 486720 KB Output is correct
101 Correct 5266 ms 498652 KB Output is correct
102 Correct 3921 ms 498652 KB Output is correct
103 Correct 3836 ms 498652 KB Output is correct
104 Correct 3922 ms 498652 KB Output is correct
105 Correct 3842 ms 507236 KB Output is correct
106 Correct 3926 ms 563880 KB Output is correct
107 Correct 3789 ms 578620 KB Output is correct
108 Correct 3773 ms 578620 KB Output is correct
109 Correct 3723 ms 578620 KB Output is correct
110 Correct 3034 ms 613396 KB Output is correct
111 Correct 3104 ms 627888 KB Output is correct
112 Correct 3211 ms 638972 KB Output is correct
113 Correct 3455 ms 638972 KB Output is correct
114 Correct 3552 ms 638972 KB Output is correct