#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 2e6 + 5;
const int mod = 1e9 + 7;
int n;
int color[N];
vi g[N];
int f[N];
int get(int k) {
return f[k] == k ? k : f[k] = get(f[k]);
}
int main(void) {
ios_base::sync_with_stdio(0);
cin>>n;
int ans = 1;
vii e(n);
for (auto & it : e)
cin>>it.fi>>it.se;
sort(all(e));
for (int i = 0;i < n + n;++i)
f[i] = i;
map < int , int > M;
for (int i = 0;i < n;++i) {
auto l = M.lower_bound(e[i].fi);
auto r = M.lower_bound(e[i].se);
if (!M.empty()) {
int lst;
if (r != M.begin()) {
--r;
lst = get(r->se);
++r;
} else {
lst = get(r->se);
}
while (l != r) {
f[get(l->se + n)] = get(i);
f[get(l->se)] = get(i + n);
if (get(l->se) == get(lst))
break;
++l;
}
}
M[e[i].se] = i;
}
set < int > ss;
for (int i = 0;i < n;++i)
if (get(i) == get(i + n))
ans = 0;
for (int i = 0;i < n + n;++i)
ss.insert(get(i));
for (int i = 0;i < ss.size();i += 2)
ans = (ans * 2) % mod;
cout << ans << '\n';
return 0;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0;i < ss.size();i += 2)
~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
47224 KB |
Output is correct |
2 |
Correct |
53 ms |
47336 KB |
Output is correct |
3 |
Correct |
53 ms |
47376 KB |
Output is correct |
4 |
Correct |
45 ms |
47556 KB |
Output is correct |
5 |
Correct |
46 ms |
47556 KB |
Output is correct |
6 |
Correct |
45 ms |
47560 KB |
Output is correct |
7 |
Correct |
48 ms |
47564 KB |
Output is correct |
8 |
Correct |
44 ms |
47740 KB |
Output is correct |
9 |
Correct |
50 ms |
47740 KB |
Output is correct |
10 |
Correct |
46 ms |
47740 KB |
Output is correct |
11 |
Correct |
44 ms |
47740 KB |
Output is correct |
12 |
Correct |
46 ms |
47740 KB |
Output is correct |
13 |
Correct |
53 ms |
47740 KB |
Output is correct |
14 |
Correct |
52 ms |
47744 KB |
Output is correct |
15 |
Correct |
47 ms |
47768 KB |
Output is correct |
16 |
Correct |
56 ms |
47768 KB |
Output is correct |
17 |
Correct |
45 ms |
47768 KB |
Output is correct |
18 |
Correct |
42 ms |
47768 KB |
Output is correct |
19 |
Correct |
46 ms |
47768 KB |
Output is correct |
20 |
Correct |
45 ms |
47896 KB |
Output is correct |
21 |
Correct |
52 ms |
47896 KB |
Output is correct |
22 |
Correct |
53 ms |
47896 KB |
Output is correct |
23 |
Correct |
50 ms |
47896 KB |
Output is correct |
24 |
Correct |
52 ms |
47896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
47224 KB |
Output is correct |
2 |
Correct |
53 ms |
47336 KB |
Output is correct |
3 |
Correct |
53 ms |
47376 KB |
Output is correct |
4 |
Correct |
45 ms |
47556 KB |
Output is correct |
5 |
Correct |
46 ms |
47556 KB |
Output is correct |
6 |
Correct |
45 ms |
47560 KB |
Output is correct |
7 |
Correct |
48 ms |
47564 KB |
Output is correct |
8 |
Correct |
44 ms |
47740 KB |
Output is correct |
9 |
Correct |
50 ms |
47740 KB |
Output is correct |
10 |
Correct |
46 ms |
47740 KB |
Output is correct |
11 |
Correct |
44 ms |
47740 KB |
Output is correct |
12 |
Correct |
46 ms |
47740 KB |
Output is correct |
13 |
Correct |
53 ms |
47740 KB |
Output is correct |
14 |
Correct |
52 ms |
47744 KB |
Output is correct |
15 |
Correct |
47 ms |
47768 KB |
Output is correct |
16 |
Correct |
56 ms |
47768 KB |
Output is correct |
17 |
Correct |
45 ms |
47768 KB |
Output is correct |
18 |
Correct |
42 ms |
47768 KB |
Output is correct |
19 |
Correct |
46 ms |
47768 KB |
Output is correct |
20 |
Correct |
45 ms |
47896 KB |
Output is correct |
21 |
Correct |
52 ms |
47896 KB |
Output is correct |
22 |
Correct |
53 ms |
47896 KB |
Output is correct |
23 |
Correct |
50 ms |
47896 KB |
Output is correct |
24 |
Correct |
52 ms |
47896 KB |
Output is correct |
25 |
Correct |
54 ms |
47912 KB |
Output is correct |
26 |
Correct |
58 ms |
47936 KB |
Output is correct |
27 |
Correct |
53 ms |
48068 KB |
Output is correct |
28 |
Correct |
47 ms |
48200 KB |
Output is correct |
29 |
Correct |
47 ms |
48200 KB |
Output is correct |
30 |
Correct |
47 ms |
48200 KB |
Output is correct |
31 |
Correct |
45 ms |
48200 KB |
Output is correct |
32 |
Correct |
47 ms |
48200 KB |
Output is correct |
33 |
Correct |
45 ms |
48200 KB |
Output is correct |
34 |
Correct |
47 ms |
48200 KB |
Output is correct |
35 |
Correct |
43 ms |
48328 KB |
Output is correct |
36 |
Correct |
48 ms |
48476 KB |
Output is correct |
37 |
Correct |
54 ms |
48476 KB |
Output is correct |
38 |
Correct |
54 ms |
48476 KB |
Output is correct |
39 |
Correct |
46 ms |
48476 KB |
Output is correct |
40 |
Correct |
48 ms |
48572 KB |
Output is correct |
41 |
Correct |
45 ms |
48572 KB |
Output is correct |
42 |
Correct |
47 ms |
48572 KB |
Output is correct |
43 |
Correct |
54 ms |
48572 KB |
Output is correct |
44 |
Correct |
52 ms |
48572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
47224 KB |
Output is correct |
2 |
Correct |
53 ms |
47336 KB |
Output is correct |
3 |
Correct |
53 ms |
47376 KB |
Output is correct |
4 |
Correct |
45 ms |
47556 KB |
Output is correct |
5 |
Correct |
46 ms |
47556 KB |
Output is correct |
6 |
Correct |
45 ms |
47560 KB |
Output is correct |
7 |
Correct |
48 ms |
47564 KB |
Output is correct |
8 |
Correct |
44 ms |
47740 KB |
Output is correct |
9 |
Correct |
50 ms |
47740 KB |
Output is correct |
10 |
Correct |
46 ms |
47740 KB |
Output is correct |
11 |
Correct |
44 ms |
47740 KB |
Output is correct |
12 |
Correct |
46 ms |
47740 KB |
Output is correct |
13 |
Correct |
53 ms |
47740 KB |
Output is correct |
14 |
Correct |
52 ms |
47744 KB |
Output is correct |
15 |
Correct |
47 ms |
47768 KB |
Output is correct |
16 |
Correct |
56 ms |
47768 KB |
Output is correct |
17 |
Correct |
45 ms |
47768 KB |
Output is correct |
18 |
Correct |
42 ms |
47768 KB |
Output is correct |
19 |
Correct |
46 ms |
47768 KB |
Output is correct |
20 |
Correct |
45 ms |
47896 KB |
Output is correct |
21 |
Correct |
52 ms |
47896 KB |
Output is correct |
22 |
Correct |
53 ms |
47896 KB |
Output is correct |
23 |
Correct |
50 ms |
47896 KB |
Output is correct |
24 |
Correct |
52 ms |
47896 KB |
Output is correct |
25 |
Correct |
54 ms |
47912 KB |
Output is correct |
26 |
Correct |
58 ms |
47936 KB |
Output is correct |
27 |
Correct |
53 ms |
48068 KB |
Output is correct |
28 |
Correct |
47 ms |
48200 KB |
Output is correct |
29 |
Correct |
47 ms |
48200 KB |
Output is correct |
30 |
Correct |
47 ms |
48200 KB |
Output is correct |
31 |
Correct |
45 ms |
48200 KB |
Output is correct |
32 |
Correct |
47 ms |
48200 KB |
Output is correct |
33 |
Correct |
45 ms |
48200 KB |
Output is correct |
34 |
Correct |
47 ms |
48200 KB |
Output is correct |
35 |
Correct |
43 ms |
48328 KB |
Output is correct |
36 |
Correct |
48 ms |
48476 KB |
Output is correct |
37 |
Correct |
54 ms |
48476 KB |
Output is correct |
38 |
Correct |
54 ms |
48476 KB |
Output is correct |
39 |
Correct |
46 ms |
48476 KB |
Output is correct |
40 |
Correct |
48 ms |
48572 KB |
Output is correct |
41 |
Correct |
45 ms |
48572 KB |
Output is correct |
42 |
Correct |
47 ms |
48572 KB |
Output is correct |
43 |
Correct |
54 ms |
48572 KB |
Output is correct |
44 |
Correct |
52 ms |
48572 KB |
Output is correct |
45 |
Correct |
173 ms |
57840 KB |
Output is correct |
46 |
Correct |
164 ms |
58980 KB |
Output is correct |
47 |
Correct |
207 ms |
60264 KB |
Output is correct |
48 |
Correct |
169 ms |
61584 KB |
Output is correct |
49 |
Correct |
174 ms |
62784 KB |
Output is correct |
50 |
Correct |
174 ms |
64072 KB |
Output is correct |
51 |
Correct |
155 ms |
65312 KB |
Output is correct |
52 |
Correct |
199 ms |
74112 KB |
Output is correct |
53 |
Correct |
213 ms |
75248 KB |
Output is correct |
54 |
Correct |
138 ms |
75248 KB |
Output is correct |
55 |
Correct |
135 ms |
75248 KB |
Output is correct |
56 |
Correct |
149 ms |
75248 KB |
Output is correct |
57 |
Correct |
222 ms |
75568 KB |
Output is correct |
58 |
Correct |
196 ms |
81564 KB |
Output is correct |
59 |
Correct |
163 ms |
82056 KB |
Output is correct |
60 |
Correct |
176 ms |
82056 KB |
Output is correct |
61 |
Correct |
150 ms |
82056 KB |
Output is correct |
62 |
Correct |
229 ms |
83540 KB |
Output is correct |
63 |
Correct |
156 ms |
83540 KB |
Output is correct |
64 |
Correct |
153 ms |
83540 KB |
Output is correct |
65 |
Correct |
171 ms |
83540 KB |
Output is correct |
66 |
Correct |
190 ms |
83540 KB |
Output is correct |
67 |
Correct |
165 ms |
83556 KB |
Output is correct |
68 |
Correct |
139 ms |
84900 KB |
Output is correct |
69 |
Correct |
147 ms |
86132 KB |
Output is correct |
70 |
Correct |
140 ms |
87332 KB |
Output is correct |
71 |
Correct |
139 ms |
89460 KB |
Output is correct |
72 |
Correct |
150 ms |
90696 KB |
Output is correct |
73 |
Correct |
144 ms |
92208 KB |
Output is correct |
74 |
Correct |
138 ms |
93556 KB |
Output is correct |
75 |
Correct |
151 ms |
95232 KB |
Output is correct |
76 |
Correct |
161 ms |
96536 KB |
Output is correct |
77 |
Correct |
151 ms |
97940 KB |
Output is correct |
78 |
Correct |
159 ms |
99504 KB |
Output is correct |
79 |
Correct |
151 ms |
100936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
47224 KB |
Output is correct |
2 |
Correct |
53 ms |
47336 KB |
Output is correct |
3 |
Correct |
53 ms |
47376 KB |
Output is correct |
4 |
Correct |
45 ms |
47556 KB |
Output is correct |
5 |
Correct |
46 ms |
47556 KB |
Output is correct |
6 |
Correct |
45 ms |
47560 KB |
Output is correct |
7 |
Correct |
48 ms |
47564 KB |
Output is correct |
8 |
Correct |
44 ms |
47740 KB |
Output is correct |
9 |
Correct |
50 ms |
47740 KB |
Output is correct |
10 |
Correct |
46 ms |
47740 KB |
Output is correct |
11 |
Correct |
44 ms |
47740 KB |
Output is correct |
12 |
Correct |
46 ms |
47740 KB |
Output is correct |
13 |
Correct |
53 ms |
47740 KB |
Output is correct |
14 |
Correct |
52 ms |
47744 KB |
Output is correct |
15 |
Correct |
47 ms |
47768 KB |
Output is correct |
16 |
Correct |
56 ms |
47768 KB |
Output is correct |
17 |
Correct |
45 ms |
47768 KB |
Output is correct |
18 |
Correct |
42 ms |
47768 KB |
Output is correct |
19 |
Correct |
46 ms |
47768 KB |
Output is correct |
20 |
Correct |
45 ms |
47896 KB |
Output is correct |
21 |
Correct |
52 ms |
47896 KB |
Output is correct |
22 |
Correct |
53 ms |
47896 KB |
Output is correct |
23 |
Correct |
50 ms |
47896 KB |
Output is correct |
24 |
Correct |
52 ms |
47896 KB |
Output is correct |
25 |
Correct |
54 ms |
47912 KB |
Output is correct |
26 |
Correct |
58 ms |
47936 KB |
Output is correct |
27 |
Correct |
53 ms |
48068 KB |
Output is correct |
28 |
Correct |
47 ms |
48200 KB |
Output is correct |
29 |
Correct |
47 ms |
48200 KB |
Output is correct |
30 |
Correct |
47 ms |
48200 KB |
Output is correct |
31 |
Correct |
45 ms |
48200 KB |
Output is correct |
32 |
Correct |
47 ms |
48200 KB |
Output is correct |
33 |
Correct |
45 ms |
48200 KB |
Output is correct |
34 |
Correct |
47 ms |
48200 KB |
Output is correct |
35 |
Correct |
43 ms |
48328 KB |
Output is correct |
36 |
Correct |
48 ms |
48476 KB |
Output is correct |
37 |
Correct |
54 ms |
48476 KB |
Output is correct |
38 |
Correct |
54 ms |
48476 KB |
Output is correct |
39 |
Correct |
46 ms |
48476 KB |
Output is correct |
40 |
Correct |
48 ms |
48572 KB |
Output is correct |
41 |
Correct |
45 ms |
48572 KB |
Output is correct |
42 |
Correct |
47 ms |
48572 KB |
Output is correct |
43 |
Correct |
54 ms |
48572 KB |
Output is correct |
44 |
Correct |
52 ms |
48572 KB |
Output is correct |
45 |
Correct |
173 ms |
57840 KB |
Output is correct |
46 |
Correct |
164 ms |
58980 KB |
Output is correct |
47 |
Correct |
207 ms |
60264 KB |
Output is correct |
48 |
Correct |
169 ms |
61584 KB |
Output is correct |
49 |
Correct |
174 ms |
62784 KB |
Output is correct |
50 |
Correct |
174 ms |
64072 KB |
Output is correct |
51 |
Correct |
155 ms |
65312 KB |
Output is correct |
52 |
Correct |
199 ms |
74112 KB |
Output is correct |
53 |
Correct |
213 ms |
75248 KB |
Output is correct |
54 |
Correct |
138 ms |
75248 KB |
Output is correct |
55 |
Correct |
135 ms |
75248 KB |
Output is correct |
56 |
Correct |
149 ms |
75248 KB |
Output is correct |
57 |
Correct |
222 ms |
75568 KB |
Output is correct |
58 |
Correct |
196 ms |
81564 KB |
Output is correct |
59 |
Correct |
163 ms |
82056 KB |
Output is correct |
60 |
Correct |
176 ms |
82056 KB |
Output is correct |
61 |
Correct |
150 ms |
82056 KB |
Output is correct |
62 |
Correct |
229 ms |
83540 KB |
Output is correct |
63 |
Correct |
156 ms |
83540 KB |
Output is correct |
64 |
Correct |
153 ms |
83540 KB |
Output is correct |
65 |
Correct |
171 ms |
83540 KB |
Output is correct |
66 |
Correct |
190 ms |
83540 KB |
Output is correct |
67 |
Correct |
165 ms |
83556 KB |
Output is correct |
68 |
Correct |
139 ms |
84900 KB |
Output is correct |
69 |
Correct |
147 ms |
86132 KB |
Output is correct |
70 |
Correct |
140 ms |
87332 KB |
Output is correct |
71 |
Correct |
139 ms |
89460 KB |
Output is correct |
72 |
Correct |
150 ms |
90696 KB |
Output is correct |
73 |
Correct |
144 ms |
92208 KB |
Output is correct |
74 |
Correct |
138 ms |
93556 KB |
Output is correct |
75 |
Correct |
151 ms |
95232 KB |
Output is correct |
76 |
Correct |
161 ms |
96536 KB |
Output is correct |
77 |
Correct |
151 ms |
97940 KB |
Output is correct |
78 |
Correct |
159 ms |
99504 KB |
Output is correct |
79 |
Correct |
151 ms |
100936 KB |
Output is correct |
80 |
Correct |
1287 ms |
189532 KB |
Output is correct |
81 |
Correct |
1247 ms |
203928 KB |
Output is correct |
82 |
Correct |
1242 ms |
217668 KB |
Output is correct |
83 |
Correct |
1283 ms |
231336 KB |
Output is correct |
84 |
Correct |
1488 ms |
244964 KB |
Output is correct |
85 |
Correct |
1391 ms |
258696 KB |
Output is correct |
86 |
Correct |
1406 ms |
271552 KB |
Output is correct |
87 |
Correct |
2572 ms |
350784 KB |
Output is correct |
88 |
Correct |
2213 ms |
364116 KB |
Output is correct |
89 |
Correct |
1293 ms |
364116 KB |
Output is correct |
90 |
Correct |
1306 ms |
364116 KB |
Output is correct |
91 |
Correct |
1327 ms |
364116 KB |
Output is correct |
92 |
Correct |
2335 ms |
374000 KB |
Output is correct |
93 |
Correct |
2592 ms |
424564 KB |
Output is correct |
94 |
Correct |
1548 ms |
424564 KB |
Output is correct |
95 |
Correct |
1558 ms |
424564 KB |
Output is correct |
96 |
Correct |
1336 ms |
424564 KB |
Output is correct |
97 |
Correct |
1448 ms |
445000 KB |
Output is correct |
98 |
Correct |
1350 ms |
445000 KB |
Output is correct |
99 |
Correct |
1287 ms |
445000 KB |
Output is correct |
100 |
Correct |
2675 ms |
445000 KB |
Output is correct |
101 |
Correct |
2785 ms |
445000 KB |
Output is correct |
102 |
Correct |
1525 ms |
453148 KB |
Output is correct |
103 |
Correct |
1752 ms |
463572 KB |
Output is correct |
104 |
Correct |
1568 ms |
474028 KB |
Output is correct |
105 |
Correct |
1620 ms |
484220 KB |
Output is correct |
106 |
Correct |
1797 ms |
499992 KB |
Output is correct |
107 |
Correct |
1877 ms |
510076 KB |
Output is correct |
108 |
Correct |
1656 ms |
521696 KB |
Output is correct |
109 |
Correct |
1700 ms |
531424 KB |
Output is correct |
110 |
Correct |
1662 ms |
544588 KB |
Output is correct |
111 |
Correct |
1585 ms |
553988 KB |
Output is correct |
112 |
Correct |
1637 ms |
563676 KB |
Output is correct |
113 |
Correct |
1258 ms |
575748 KB |
Output is correct |
114 |
Correct |
1326 ms |
585136 KB |
Output is correct |