#include <bits/stdc++.h>
#define kyou using
#define mo namespace
#define kawaii std
kyou mo kawaii; // hi honey~
#define ll long long
#define ld long double
#define endl "\n"
const int MX = 1000005;
const int LG = 5;
const int BLOCK = 205;
const int inf = 1000000069;
const ll inf_ll = 4000000000000000069ll;
const ll mod = 1e9 + 7;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {0, 1, 0, -1, 0, 0};
const int dy[] = {1, 0, -1, 0, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1}; // 3d
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag
bool untied = 0;
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
if(!untied) unsyncIO(), untied = 1;
if(s.size()){
setIn(s + ".in");
setOut(s + "_output.out");
}
}
int n;
vector<pair<int, int> > v;
int par[MX * 2], used[MX * 2];
map<int, int> mp;
int find(int x){
if(par[x] < 0) return x;
return par[x] = find(par[x]);
}
void uni(int x, int y){
if((x = find(x)) == (y = find(y))) return;
if(par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
}
int main(){
setIO();
cin >> n;
v.resize(n);
for(int i = 0; i < n; i ++){
cin >> v[i].first >> v[i].second;
par[i] = par[i + n] = -1;
}
sort(v.begin(), v.end());
for(int i = 0; i < n; i ++){
for(auto itL = mp.lower_bound(v[i].first), itR = mp.lower_bound(v[i].second); itL != itR; itL ++, itR ++){
uni(i, (itL -> second) + n);
uni(i + n, (itL -> second));
if(find((-- itR) -> second) == find(itL -> second)) break;
}
mp[v[i].second] = i;
}
int ans = 1;
for(int i = 0; i < n; i ++){
if(find(i) == find(i + n)) ans = 0;
else used[find(i)] = used[find(i + n)] = 1;
}
for(int i = 0; i < n; i ++)
if(used[i]) (ans += ans) %= mod;
cout << ans << endl;
return 0;
}
Compilation message
port_facility.cpp: In function 'void setIn(std::string)':
port_facility.cpp:27:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'void setOut(std::string)':
port_facility.cpp:28:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
324 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
324 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
460 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
2 ms |
464 KB |
Output is correct |
33 |
Correct |
2 ms |
460 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
460 KB |
Output is correct |
37 |
Correct |
2 ms |
460 KB |
Output is correct |
38 |
Correct |
2 ms |
460 KB |
Output is correct |
39 |
Correct |
3 ms |
460 KB |
Output is correct |
40 |
Correct |
2 ms |
460 KB |
Output is correct |
41 |
Correct |
2 ms |
460 KB |
Output is correct |
42 |
Correct |
3 ms |
460 KB |
Output is correct |
43 |
Correct |
3 ms |
460 KB |
Output is correct |
44 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
324 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
460 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
2 ms |
464 KB |
Output is correct |
33 |
Correct |
2 ms |
460 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
460 KB |
Output is correct |
37 |
Correct |
2 ms |
460 KB |
Output is correct |
38 |
Correct |
2 ms |
460 KB |
Output is correct |
39 |
Correct |
3 ms |
460 KB |
Output is correct |
40 |
Correct |
2 ms |
460 KB |
Output is correct |
41 |
Correct |
2 ms |
460 KB |
Output is correct |
42 |
Correct |
3 ms |
460 KB |
Output is correct |
43 |
Correct |
3 ms |
460 KB |
Output is correct |
44 |
Correct |
2 ms |
376 KB |
Output is correct |
45 |
Correct |
73 ms |
8544 KB |
Output is correct |
46 |
Correct |
87 ms |
8528 KB |
Output is correct |
47 |
Correct |
76 ms |
8572 KB |
Output is correct |
48 |
Correct |
73 ms |
8540 KB |
Output is correct |
49 |
Correct |
73 ms |
8516 KB |
Output is correct |
50 |
Correct |
72 ms |
8552 KB |
Output is correct |
51 |
Correct |
70 ms |
8524 KB |
Output is correct |
52 |
Correct |
76 ms |
8604 KB |
Output is correct |
53 |
Correct |
75 ms |
8600 KB |
Output is correct |
54 |
Correct |
67 ms |
7784 KB |
Output is correct |
55 |
Correct |
68 ms |
7884 KB |
Output is correct |
56 |
Correct |
67 ms |
7876 KB |
Output is correct |
57 |
Correct |
74 ms |
8620 KB |
Output is correct |
58 |
Correct |
81 ms |
8548 KB |
Output is correct |
59 |
Correct |
67 ms |
8516 KB |
Output is correct |
60 |
Correct |
72 ms |
8644 KB |
Output is correct |
61 |
Correct |
70 ms |
8516 KB |
Output is correct |
62 |
Correct |
65 ms |
8516 KB |
Output is correct |
63 |
Correct |
71 ms |
8516 KB |
Output is correct |
64 |
Correct |
72 ms |
8660 KB |
Output is correct |
65 |
Correct |
100 ms |
7776 KB |
Output is correct |
66 |
Correct |
85 ms |
7840 KB |
Output is correct |
67 |
Correct |
82 ms |
7864 KB |
Output is correct |
68 |
Correct |
87 ms |
7744 KB |
Output is correct |
69 |
Correct |
73 ms |
7804 KB |
Output is correct |
70 |
Correct |
74 ms |
7836 KB |
Output is correct |
71 |
Correct |
77 ms |
7748 KB |
Output is correct |
72 |
Correct |
91 ms |
7792 KB |
Output is correct |
73 |
Correct |
97 ms |
7748 KB |
Output is correct |
74 |
Correct |
77 ms |
7760 KB |
Output is correct |
75 |
Correct |
75 ms |
7764 KB |
Output is correct |
76 |
Correct |
73 ms |
7744 KB |
Output is correct |
77 |
Correct |
73 ms |
7804 KB |
Output is correct |
78 |
Correct |
73 ms |
8560 KB |
Output is correct |
79 |
Correct |
73 ms |
8580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
324 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
460 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
2 ms |
464 KB |
Output is correct |
33 |
Correct |
2 ms |
460 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
460 KB |
Output is correct |
37 |
Correct |
2 ms |
460 KB |
Output is correct |
38 |
Correct |
2 ms |
460 KB |
Output is correct |
39 |
Correct |
3 ms |
460 KB |
Output is correct |
40 |
Correct |
2 ms |
460 KB |
Output is correct |
41 |
Correct |
2 ms |
460 KB |
Output is correct |
42 |
Correct |
3 ms |
460 KB |
Output is correct |
43 |
Correct |
3 ms |
460 KB |
Output is correct |
44 |
Correct |
2 ms |
376 KB |
Output is correct |
45 |
Correct |
73 ms |
8544 KB |
Output is correct |
46 |
Correct |
87 ms |
8528 KB |
Output is correct |
47 |
Correct |
76 ms |
8572 KB |
Output is correct |
48 |
Correct |
73 ms |
8540 KB |
Output is correct |
49 |
Correct |
73 ms |
8516 KB |
Output is correct |
50 |
Correct |
72 ms |
8552 KB |
Output is correct |
51 |
Correct |
70 ms |
8524 KB |
Output is correct |
52 |
Correct |
76 ms |
8604 KB |
Output is correct |
53 |
Correct |
75 ms |
8600 KB |
Output is correct |
54 |
Correct |
67 ms |
7784 KB |
Output is correct |
55 |
Correct |
68 ms |
7884 KB |
Output is correct |
56 |
Correct |
67 ms |
7876 KB |
Output is correct |
57 |
Correct |
74 ms |
8620 KB |
Output is correct |
58 |
Correct |
81 ms |
8548 KB |
Output is correct |
59 |
Correct |
67 ms |
8516 KB |
Output is correct |
60 |
Correct |
72 ms |
8644 KB |
Output is correct |
61 |
Correct |
70 ms |
8516 KB |
Output is correct |
62 |
Correct |
65 ms |
8516 KB |
Output is correct |
63 |
Correct |
71 ms |
8516 KB |
Output is correct |
64 |
Correct |
72 ms |
8660 KB |
Output is correct |
65 |
Correct |
100 ms |
7776 KB |
Output is correct |
66 |
Correct |
85 ms |
7840 KB |
Output is correct |
67 |
Correct |
82 ms |
7864 KB |
Output is correct |
68 |
Correct |
87 ms |
7744 KB |
Output is correct |
69 |
Correct |
73 ms |
7804 KB |
Output is correct |
70 |
Correct |
74 ms |
7836 KB |
Output is correct |
71 |
Correct |
77 ms |
7748 KB |
Output is correct |
72 |
Correct |
91 ms |
7792 KB |
Output is correct |
73 |
Correct |
97 ms |
7748 KB |
Output is correct |
74 |
Correct |
77 ms |
7760 KB |
Output is correct |
75 |
Correct |
75 ms |
7764 KB |
Output is correct |
76 |
Correct |
73 ms |
7744 KB |
Output is correct |
77 |
Correct |
73 ms |
7804 KB |
Output is correct |
78 |
Correct |
73 ms |
8560 KB |
Output is correct |
79 |
Correct |
73 ms |
8580 KB |
Output is correct |
80 |
Correct |
836 ms |
85376 KB |
Output is correct |
81 |
Correct |
783 ms |
85280 KB |
Output is correct |
82 |
Correct |
794 ms |
85316 KB |
Output is correct |
83 |
Correct |
768 ms |
85196 KB |
Output is correct |
84 |
Correct |
768 ms |
85240 KB |
Output is correct |
85 |
Correct |
776 ms |
85192 KB |
Output is correct |
86 |
Correct |
769 ms |
85300 KB |
Output is correct |
87 |
Correct |
904 ms |
85364 KB |
Output is correct |
88 |
Correct |
876 ms |
85232 KB |
Output is correct |
89 |
Correct |
841 ms |
77596 KB |
Output is correct |
90 |
Correct |
819 ms |
77540 KB |
Output is correct |
91 |
Correct |
857 ms |
77524 KB |
Output is correct |
92 |
Correct |
917 ms |
85380 KB |
Output is correct |
93 |
Correct |
907 ms |
85316 KB |
Output is correct |
94 |
Correct |
743 ms |
85316 KB |
Output is correct |
95 |
Correct |
764 ms |
85224 KB |
Output is correct |
96 |
Correct |
785 ms |
85368 KB |
Output is correct |
97 |
Correct |
741 ms |
85272 KB |
Output is correct |
98 |
Correct |
767 ms |
85448 KB |
Output is correct |
99 |
Correct |
767 ms |
85368 KB |
Output is correct |
100 |
Correct |
1470 ms |
77508 KB |
Output is correct |
101 |
Correct |
1485 ms |
77476 KB |
Output is correct |
102 |
Correct |
924 ms |
77492 KB |
Output is correct |
103 |
Correct |
941 ms |
77488 KB |
Output is correct |
104 |
Correct |
924 ms |
77436 KB |
Output is correct |
105 |
Correct |
929 ms |
77648 KB |
Output is correct |
106 |
Correct |
967 ms |
77552 KB |
Output is correct |
107 |
Correct |
985 ms |
77496 KB |
Output is correct |
108 |
Correct |
974 ms |
77628 KB |
Output is correct |
109 |
Correct |
963 ms |
77508 KB |
Output is correct |
110 |
Correct |
930 ms |
77396 KB |
Output is correct |
111 |
Correct |
942 ms |
77668 KB |
Output is correct |
112 |
Correct |
950 ms |
77456 KB |
Output is correct |
113 |
Correct |
863 ms |
85212 KB |
Output is correct |
114 |
Correct |
816 ms |
85292 KB |
Output is correct |