# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
69351 | 2018-08-20T15:14:59 Z | Just_Solve_The_Problem | Port Facility (JOI17_port_facility) | C++11 | 2173 ms | 624352 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back #define eb emplace_back #define ll long long #define pii pair < int, int > #define fr first #define sc second #define mk make_pair #define sz(s) (int)s.size() #define all(s) s.begin(), s.end() #define OK puts("ok"); #define whatis(x) cerr << #x << " = " << x << endl; #define pause system("pause"); const int N = (int)2e6 + 7; const int inf = (int)1e9 + 7; int mod = (int)1e9 + 7; pii ar[N]; int pr[N], used[N]; int ans; map < int, int > mp; int mult(int a, int b) { return (a * 1LL * b) % mod; } int getpar(int a) { if (pr[a] == a) return a; return pr[a] = getpar(pr[a]); } void connect(int a, int b) { a = getpar(a); b = getpar(b); if (a != b) { pr[a] = b; } } main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &ar[i].fr, &ar[i].sc); } iota(pr, pr + n + n + 2, 0); sort(ar, ar + n); int ans = 1; for (int i = 0; i < n; i++) { auto fir = mp.lower_bound(ar[i].fr), sec = mp.lower_bound(ar[i].sc); while (fir != sec) { connect(i, (fir -> sc) + n); connect(i + n, fir -> sc); if (getpar((--sec) -> sc) == getpar(fir -> sc)) break; fir++; sec++; } mp[ar[i].sc] = i; } for (int i = 0; i < n; i++) { if (getpar(i) == getpar(i + n)) ans = 0; else used[getpar(i)] = used[getpar(i + n)] = 1; } for (int i = 0; i < n; i++) { if (used[i]) { ans = mult(ans, 2); } } cout << ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 452 KB | Output is correct |
3 | Correct | 3 ms | 452 KB | Output is correct |
4 | Correct | 3 ms | 452 KB | Output is correct |
5 | Correct | 2 ms | 568 KB | Output is correct |
6 | Correct | 3 ms | 576 KB | Output is correct |
7 | Correct | 3 ms | 696 KB | Output is correct |
8 | Correct | 3 ms | 696 KB | Output is correct |
9 | Correct | 2 ms | 708 KB | Output is correct |
10 | Correct | 2 ms | 712 KB | Output is correct |
11 | Correct | 3 ms | 712 KB | Output is correct |
12 | Correct | 2 ms | 712 KB | Output is correct |
13 | Correct | 3 ms | 724 KB | Output is correct |
14 | Correct | 3 ms | 724 KB | Output is correct |
15 | Correct | 3 ms | 724 KB | Output is correct |
16 | Correct | 2 ms | 724 KB | Output is correct |
17 | Correct | 3 ms | 724 KB | Output is correct |
18 | Correct | 2 ms | 724 KB | Output is correct |
19 | Correct | 4 ms | 724 KB | Output is correct |
20 | Correct | 3 ms | 724 KB | Output is correct |
21 | Correct | 4 ms | 724 KB | Output is correct |
22 | Correct | 3 ms | 724 KB | Output is correct |
23 | Correct | 2 ms | 724 KB | Output is correct |
24 | Correct | 2 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 452 KB | Output is correct |
3 | Correct | 3 ms | 452 KB | Output is correct |
4 | Correct | 3 ms | 452 KB | Output is correct |
5 | Correct | 2 ms | 568 KB | Output is correct |
6 | Correct | 3 ms | 576 KB | Output is correct |
7 | Correct | 3 ms | 696 KB | Output is correct |
8 | Correct | 3 ms | 696 KB | Output is correct |
9 | Correct | 2 ms | 708 KB | Output is correct |
10 | Correct | 2 ms | 712 KB | Output is correct |
11 | Correct | 3 ms | 712 KB | Output is correct |
12 | Correct | 2 ms | 712 KB | Output is correct |
13 | Correct | 3 ms | 724 KB | Output is correct |
14 | Correct | 3 ms | 724 KB | Output is correct |
15 | Correct | 3 ms | 724 KB | Output is correct |
16 | Correct | 2 ms | 724 KB | Output is correct |
17 | Correct | 3 ms | 724 KB | Output is correct |
18 | Correct | 2 ms | 724 KB | Output is correct |
19 | Correct | 4 ms | 724 KB | Output is correct |
20 | Correct | 3 ms | 724 KB | Output is correct |
21 | Correct | 4 ms | 724 KB | Output is correct |
22 | Correct | 3 ms | 724 KB | Output is correct |
23 | Correct | 2 ms | 724 KB | Output is correct |
24 | Correct | 2 ms | 724 KB | Output is correct |
25 | Correct | 4 ms | 748 KB | Output is correct |
26 | Correct | 5 ms | 748 KB | Output is correct |
27 | Correct | 6 ms | 748 KB | Output is correct |
28 | Correct | 4 ms | 748 KB | Output is correct |
29 | Correct | 5 ms | 748 KB | Output is correct |
30 | Correct | 5 ms | 748 KB | Output is correct |
31 | Correct | 5 ms | 748 KB | Output is correct |
32 | Correct | 5 ms | 748 KB | Output is correct |
33 | Correct | 5 ms | 876 KB | Output is correct |
34 | Correct | 4 ms | 876 KB | Output is correct |
35 | Correct | 4 ms | 876 KB | Output is correct |
36 | Correct | 5 ms | 876 KB | Output is correct |
37 | Correct | 4 ms | 876 KB | Output is correct |
38 | Correct | 5 ms | 876 KB | Output is correct |
39 | Correct | 4 ms | 876 KB | Output is correct |
40 | Correct | 4 ms | 876 KB | Output is correct |
41 | Correct | 5 ms | 876 KB | Output is correct |
42 | Correct | 4 ms | 876 KB | Output is correct |
43 | Correct | 4 ms | 876 KB | Output is correct |
44 | Correct | 4 ms | 876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 452 KB | Output is correct |
3 | Correct | 3 ms | 452 KB | Output is correct |
4 | Correct | 3 ms | 452 KB | Output is correct |
5 | Correct | 2 ms | 568 KB | Output is correct |
6 | Correct | 3 ms | 576 KB | Output is correct |
7 | Correct | 3 ms | 696 KB | Output is correct |
8 | Correct | 3 ms | 696 KB | Output is correct |
9 | Correct | 2 ms | 708 KB | Output is correct |
10 | Correct | 2 ms | 712 KB | Output is correct |
11 | Correct | 3 ms | 712 KB | Output is correct |
12 | Correct | 2 ms | 712 KB | Output is correct |
13 | Correct | 3 ms | 724 KB | Output is correct |
14 | Correct | 3 ms | 724 KB | Output is correct |
15 | Correct | 3 ms | 724 KB | Output is correct |
16 | Correct | 2 ms | 724 KB | Output is correct |
17 | Correct | 3 ms | 724 KB | Output is correct |
18 | Correct | 2 ms | 724 KB | Output is correct |
19 | Correct | 4 ms | 724 KB | Output is correct |
20 | Correct | 3 ms | 724 KB | Output is correct |
21 | Correct | 4 ms | 724 KB | Output is correct |
22 | Correct | 3 ms | 724 KB | Output is correct |
23 | Correct | 2 ms | 724 KB | Output is correct |
24 | Correct | 2 ms | 724 KB | Output is correct |
25 | Correct | 4 ms | 748 KB | Output is correct |
26 | Correct | 5 ms | 748 KB | Output is correct |
27 | Correct | 6 ms | 748 KB | Output is correct |
28 | Correct | 4 ms | 748 KB | Output is correct |
29 | Correct | 5 ms | 748 KB | Output is correct |
30 | Correct | 5 ms | 748 KB | Output is correct |
31 | Correct | 5 ms | 748 KB | Output is correct |
32 | Correct | 5 ms | 748 KB | Output is correct |
33 | Correct | 5 ms | 876 KB | Output is correct |
34 | Correct | 4 ms | 876 KB | Output is correct |
35 | Correct | 4 ms | 876 KB | Output is correct |
36 | Correct | 5 ms | 876 KB | Output is correct |
37 | Correct | 4 ms | 876 KB | Output is correct |
38 | Correct | 5 ms | 876 KB | Output is correct |
39 | Correct | 4 ms | 876 KB | Output is correct |
40 | Correct | 4 ms | 876 KB | Output is correct |
41 | Correct | 5 ms | 876 KB | Output is correct |
42 | Correct | 4 ms | 876 KB | Output is correct |
43 | Correct | 4 ms | 876 KB | Output is correct |
44 | Correct | 4 ms | 876 KB | Output is correct |
45 | Correct | 100 ms | 7720 KB | Output is correct |
46 | Correct | 101 ms | 8956 KB | Output is correct |
47 | Correct | 95 ms | 10236 KB | Output is correct |
48 | Correct | 107 ms | 11496 KB | Output is correct |
49 | Correct | 109 ms | 12756 KB | Output is correct |
50 | Correct | 91 ms | 14028 KB | Output is correct |
51 | Correct | 87 ms | 15192 KB | Output is correct |
52 | Correct | 115 ms | 16580 KB | Output is correct |
53 | Correct | 101 ms | 17784 KB | Output is correct |
54 | Correct | 99 ms | 18348 KB | Output is correct |
55 | Correct | 95 ms | 19580 KB | Output is correct |
56 | Correct | 105 ms | 21012 KB | Output is correct |
57 | Correct | 121 ms | 22960 KB | Output is correct |
58 | Correct | 114 ms | 24256 KB | Output is correct |
59 | Correct | 96 ms | 25484 KB | Output is correct |
60 | Correct | 114 ms | 26888 KB | Output is correct |
61 | Correct | 90 ms | 28048 KB | Output is correct |
62 | Correct | 93 ms | 29308 KB | Output is correct |
63 | Correct | 91 ms | 30688 KB | Output is correct |
64 | Correct | 96 ms | 31820 KB | Output is correct |
65 | Correct | 125 ms | 32316 KB | Output is correct |
66 | Correct | 121 ms | 33596 KB | Output is correct |
67 | Correct | 118 ms | 35604 KB | Output is correct |
68 | Correct | 112 ms | 36884 KB | Output is correct |
69 | Correct | 106 ms | 37952 KB | Output is correct |
70 | Correct | 108 ms | 39212 KB | Output is correct |
71 | Correct | 148 ms | 40600 KB | Output is correct |
72 | Correct | 141 ms | 41988 KB | Output is correct |
73 | Correct | 113 ms | 42960 KB | Output is correct |
74 | Correct | 129 ms | 44236 KB | Output is correct |
75 | Correct | 126 ms | 44828 KB | Output is correct |
76 | Correct | 109 ms | 46096 KB | Output is correct |
77 | Correct | 124 ms | 47364 KB | Output is correct |
78 | Correct | 125 ms | 49408 KB | Output is correct |
79 | Correct | 90 ms | 50784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 452 KB | Output is correct |
3 | Correct | 3 ms | 452 KB | Output is correct |
4 | Correct | 3 ms | 452 KB | Output is correct |
5 | Correct | 2 ms | 568 KB | Output is correct |
6 | Correct | 3 ms | 576 KB | Output is correct |
7 | Correct | 3 ms | 696 KB | Output is correct |
8 | Correct | 3 ms | 696 KB | Output is correct |
9 | Correct | 2 ms | 708 KB | Output is correct |
10 | Correct | 2 ms | 712 KB | Output is correct |
11 | Correct | 3 ms | 712 KB | Output is correct |
12 | Correct | 2 ms | 712 KB | Output is correct |
13 | Correct | 3 ms | 724 KB | Output is correct |
14 | Correct | 3 ms | 724 KB | Output is correct |
15 | Correct | 3 ms | 724 KB | Output is correct |
16 | Correct | 2 ms | 724 KB | Output is correct |
17 | Correct | 3 ms | 724 KB | Output is correct |
18 | Correct | 2 ms | 724 KB | Output is correct |
19 | Correct | 4 ms | 724 KB | Output is correct |
20 | Correct | 3 ms | 724 KB | Output is correct |
21 | Correct | 4 ms | 724 KB | Output is correct |
22 | Correct | 3 ms | 724 KB | Output is correct |
23 | Correct | 2 ms | 724 KB | Output is correct |
24 | Correct | 2 ms | 724 KB | Output is correct |
25 | Correct | 4 ms | 748 KB | Output is correct |
26 | Correct | 5 ms | 748 KB | Output is correct |
27 | Correct | 6 ms | 748 KB | Output is correct |
28 | Correct | 4 ms | 748 KB | Output is correct |
29 | Correct | 5 ms | 748 KB | Output is correct |
30 | Correct | 5 ms | 748 KB | Output is correct |
31 | Correct | 5 ms | 748 KB | Output is correct |
32 | Correct | 5 ms | 748 KB | Output is correct |
33 | Correct | 5 ms | 876 KB | Output is correct |
34 | Correct | 4 ms | 876 KB | Output is correct |
35 | Correct | 4 ms | 876 KB | Output is correct |
36 | Correct | 5 ms | 876 KB | Output is correct |
37 | Correct | 4 ms | 876 KB | Output is correct |
38 | Correct | 5 ms | 876 KB | Output is correct |
39 | Correct | 4 ms | 876 KB | Output is correct |
40 | Correct | 4 ms | 876 KB | Output is correct |
41 | Correct | 5 ms | 876 KB | Output is correct |
42 | Correct | 4 ms | 876 KB | Output is correct |
43 | Correct | 4 ms | 876 KB | Output is correct |
44 | Correct | 4 ms | 876 KB | Output is correct |
45 | Correct | 100 ms | 7720 KB | Output is correct |
46 | Correct | 101 ms | 8956 KB | Output is correct |
47 | Correct | 95 ms | 10236 KB | Output is correct |
48 | Correct | 107 ms | 11496 KB | Output is correct |
49 | Correct | 109 ms | 12756 KB | Output is correct |
50 | Correct | 91 ms | 14028 KB | Output is correct |
51 | Correct | 87 ms | 15192 KB | Output is correct |
52 | Correct | 115 ms | 16580 KB | Output is correct |
53 | Correct | 101 ms | 17784 KB | Output is correct |
54 | Correct | 99 ms | 18348 KB | Output is correct |
55 | Correct | 95 ms | 19580 KB | Output is correct |
56 | Correct | 105 ms | 21012 KB | Output is correct |
57 | Correct | 121 ms | 22960 KB | Output is correct |
58 | Correct | 114 ms | 24256 KB | Output is correct |
59 | Correct | 96 ms | 25484 KB | Output is correct |
60 | Correct | 114 ms | 26888 KB | Output is correct |
61 | Correct | 90 ms | 28048 KB | Output is correct |
62 | Correct | 93 ms | 29308 KB | Output is correct |
63 | Correct | 91 ms | 30688 KB | Output is correct |
64 | Correct | 96 ms | 31820 KB | Output is correct |
65 | Correct | 125 ms | 32316 KB | Output is correct |
66 | Correct | 121 ms | 33596 KB | Output is correct |
67 | Correct | 118 ms | 35604 KB | Output is correct |
68 | Correct | 112 ms | 36884 KB | Output is correct |
69 | Correct | 106 ms | 37952 KB | Output is correct |
70 | Correct | 108 ms | 39212 KB | Output is correct |
71 | Correct | 148 ms | 40600 KB | Output is correct |
72 | Correct | 141 ms | 41988 KB | Output is correct |
73 | Correct | 113 ms | 42960 KB | Output is correct |
74 | Correct | 129 ms | 44236 KB | Output is correct |
75 | Correct | 126 ms | 44828 KB | Output is correct |
76 | Correct | 109 ms | 46096 KB | Output is correct |
77 | Correct | 124 ms | 47364 KB | Output is correct |
78 | Correct | 125 ms | 49408 KB | Output is correct |
79 | Correct | 90 ms | 50784 KB | Output is correct |
80 | Correct | 1028 ms | 128904 KB | Output is correct |
81 | Correct | 1148 ms | 143632 KB | Output is correct |
82 | Correct | 1110 ms | 158092 KB | Output is correct |
83 | Correct | 1142 ms | 172596 KB | Output is correct |
84 | Correct | 1027 ms | 187364 KB | Output is correct |
85 | Correct | 1032 ms | 201708 KB | Output is correct |
86 | Correct | 1036 ms | 216384 KB | Output is correct |
87 | Correct | 1385 ms | 230964 KB | Output is correct |
88 | Correct | 1347 ms | 245444 KB | Output is correct |
89 | Correct | 1356 ms | 252272 KB | Output is correct |
90 | Correct | 1311 ms | 266804 KB | Output is correct |
91 | Correct | 1372 ms | 281440 KB | Output is correct |
92 | Correct | 1377 ms | 303828 KB | Output is correct |
93 | Correct | 1438 ms | 318400 KB | Output is correct |
94 | Correct | 979 ms | 332956 KB | Output is correct |
95 | Correct | 1120 ms | 347496 KB | Output is correct |
96 | Correct | 1051 ms | 362100 KB | Output is correct |
97 | Correct | 977 ms | 376672 KB | Output is correct |
98 | Correct | 1012 ms | 391252 KB | Output is correct |
99 | Correct | 1033 ms | 405784 KB | Output is correct |
100 | Correct | 2173 ms | 412620 KB | Output is correct |
101 | Correct | 2117 ms | 427156 KB | Output is correct |
102 | Correct | 1405 ms | 449432 KB | Output is correct |
103 | Correct | 1556 ms | 464060 KB | Output is correct |
104 | Correct | 1499 ms | 475964 KB | Output is correct |
105 | Correct | 1439 ms | 490576 KB | Output is correct |
106 | Correct | 1446 ms | 508052 KB | Output is correct |
107 | Correct | 1485 ms | 522440 KB | Output is correct |
108 | Correct | 1503 ms | 534456 KB | Output is correct |
109 | Correct | 1463 ms | 549004 KB | Output is correct |
110 | Correct | 1357 ms | 558320 KB | Output is correct |
111 | Correct | 1432 ms | 572936 KB | Output is correct |
112 | Correct | 1509 ms | 587496 KB | Output is correct |
113 | Correct | 1132 ms | 609876 KB | Output is correct |
114 | Correct | 1075 ms | 624352 KB | Output is correct |