#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int p[N], c[N];
set<pair<int,int>> s[N][2];
set<pii> S;
void rem(int x) {
for(int t = 0; t < 2; t++)
if(s[x][t].size()) S.erase(*s[x][t].begin());
}
void add(int x) {
for(int t = 0; t < 2; t++)
if(s[x][t].size()) S.insert(*s[x][t].begin());
}
void merge(int x, int y) {
if((int)s[p[x]][1].size() + (int)s[p[x]][0].size() < (int)s[p[y]][1].size() + (int)s[p[y]][0].size()) swap(x, y);
// c[x] ^ 1 --> c[y]
if(p[x] == p[y]) assert(0);
int Y = p[y], X = p[x], T = (c[x] == c[y]);
for(int t = 0; t < 2; t++) {
while(s[Y][t].size()) {
pii x = *s[Y][t].begin();
p[x.s] = X; c[x.s] = t ^ T;
s[Y][t].erase(x);
s[X][t ^ T].insert(x);
}
}
}
int l[N], r[N], vis[N];
vector<int> V[N];
void dfs(int u, int c) {
vis[u] = c;
for(int i = 0; i < V[u].size(); i++) {
if(!vis[V[u][i]]) dfs(V[u][i], 3 - c);
if(vis[V[u][i]] == vis[u]) {
cout << 0;
exit(0);
}
}
}
void add(int x, int y) {
V[x].push_back(y);
V[y].push_back(x);
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(l[i] < l[j] && r[i] < r[j] && l[j] < r[i]) add(i, j);
}
}
int ans = 1;
for(int i = 1; i <= n; i++) {
if(!vis[i]) {
dfs(i, 2);
ans = ans * 2 % mod;
}
} cout << ans;
return 0;
vector<pair<int,pair<int,int>> > x;
for(int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
x.push_back({l, {r, i}});
x.push_back({r, {0, i}});
s[i][0].insert({r, i});
p[i] = i;
}
sort(x.begin(), x.end());
vector<int> f(n + 2);
for(int i = 0; i < x.size(); i++) {
if(x[i].s.f == 0) {
int id = x[i].s.s, r = x[i].f;
rem(p[id]);
s[p[id]][c[id]].erase({r, id});
add(p[id]);
continue;
}
int r = x[i].s.f, id = x[i].s.s;
vector<int> v;
while(S.size() && (*S.begin()).f < r) {
pii x = *S.begin();
v.push_back(x.s);
if(f[p[x.s]] == i + 1) {
cout << 0;
return 0;
}
f[p[x.s]] = i + 1;
S.erase(x);
}
for(int i = 0; i < v.size(); i++) rem(p[v[i]]), merge(v[i], id);
add(p[id]);
}
for(int i = 1; i <= n; i++) if(p[i] == i) ans = ans * 2 % mod;
cout << ans;
/*
4
1 3
2 5
4 8
6 7
*/
}
Compilation message
port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
port_facility.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i < v.size(); i++) rem(p[v[i]]), merge(v[i], id);
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
117648 KB |
Output is correct |
2 |
Correct |
50 ms |
117732 KB |
Output is correct |
3 |
Correct |
53 ms |
117612 KB |
Output is correct |
4 |
Correct |
51 ms |
117680 KB |
Output is correct |
5 |
Correct |
53 ms |
117712 KB |
Output is correct |
6 |
Correct |
52 ms |
117648 KB |
Output is correct |
7 |
Correct |
52 ms |
117704 KB |
Output is correct |
8 |
Correct |
53 ms |
117732 KB |
Output is correct |
9 |
Correct |
53 ms |
117652 KB |
Output is correct |
10 |
Correct |
54 ms |
117640 KB |
Output is correct |
11 |
Correct |
52 ms |
117612 KB |
Output is correct |
12 |
Correct |
52 ms |
117732 KB |
Output is correct |
13 |
Correct |
52 ms |
117684 KB |
Output is correct |
14 |
Correct |
51 ms |
117640 KB |
Output is correct |
15 |
Correct |
54 ms |
117704 KB |
Output is correct |
16 |
Correct |
54 ms |
117708 KB |
Output is correct |
17 |
Correct |
54 ms |
117692 KB |
Output is correct |
18 |
Correct |
51 ms |
117680 KB |
Output is correct |
19 |
Correct |
53 ms |
117684 KB |
Output is correct |
20 |
Correct |
51 ms |
117716 KB |
Output is correct |
21 |
Correct |
51 ms |
117624 KB |
Output is correct |
22 |
Correct |
52 ms |
117708 KB |
Output is correct |
23 |
Correct |
52 ms |
117680 KB |
Output is correct |
24 |
Correct |
51 ms |
117640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
117648 KB |
Output is correct |
2 |
Correct |
50 ms |
117732 KB |
Output is correct |
3 |
Correct |
53 ms |
117612 KB |
Output is correct |
4 |
Correct |
51 ms |
117680 KB |
Output is correct |
5 |
Correct |
53 ms |
117712 KB |
Output is correct |
6 |
Correct |
52 ms |
117648 KB |
Output is correct |
7 |
Correct |
52 ms |
117704 KB |
Output is correct |
8 |
Correct |
53 ms |
117732 KB |
Output is correct |
9 |
Correct |
53 ms |
117652 KB |
Output is correct |
10 |
Correct |
54 ms |
117640 KB |
Output is correct |
11 |
Correct |
52 ms |
117612 KB |
Output is correct |
12 |
Correct |
52 ms |
117732 KB |
Output is correct |
13 |
Correct |
52 ms |
117684 KB |
Output is correct |
14 |
Correct |
51 ms |
117640 KB |
Output is correct |
15 |
Correct |
54 ms |
117704 KB |
Output is correct |
16 |
Correct |
54 ms |
117708 KB |
Output is correct |
17 |
Correct |
54 ms |
117692 KB |
Output is correct |
18 |
Correct |
51 ms |
117680 KB |
Output is correct |
19 |
Correct |
53 ms |
117684 KB |
Output is correct |
20 |
Correct |
51 ms |
117716 KB |
Output is correct |
21 |
Correct |
51 ms |
117624 KB |
Output is correct |
22 |
Correct |
52 ms |
117708 KB |
Output is correct |
23 |
Correct |
52 ms |
117680 KB |
Output is correct |
24 |
Correct |
51 ms |
117640 KB |
Output is correct |
25 |
Correct |
66 ms |
118048 KB |
Output is correct |
26 |
Correct |
67 ms |
118220 KB |
Output is correct |
27 |
Correct |
66 ms |
118092 KB |
Output is correct |
28 |
Correct |
66 ms |
118368 KB |
Output is correct |
29 |
Correct |
67 ms |
118220 KB |
Output is correct |
30 |
Correct |
66 ms |
118236 KB |
Output is correct |
31 |
Correct |
65 ms |
118092 KB |
Output is correct |
32 |
Correct |
67 ms |
118056 KB |
Output is correct |
33 |
Correct |
66 ms |
117964 KB |
Output is correct |
34 |
Correct |
69 ms |
118012 KB |
Output is correct |
35 |
Correct |
63 ms |
117772 KB |
Output is correct |
36 |
Correct |
66 ms |
117708 KB |
Output is correct |
37 |
Correct |
96 ms |
135180 KB |
Output is correct |
38 |
Correct |
84 ms |
126552 KB |
Output is correct |
39 |
Correct |
65 ms |
117760 KB |
Output is correct |
40 |
Correct |
67 ms |
117756 KB |
Output is correct |
41 |
Correct |
84 ms |
125900 KB |
Output is correct |
42 |
Correct |
83 ms |
126012 KB |
Output is correct |
43 |
Correct |
66 ms |
117908 KB |
Output is correct |
44 |
Correct |
66 ms |
118040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
117648 KB |
Output is correct |
2 |
Correct |
50 ms |
117732 KB |
Output is correct |
3 |
Correct |
53 ms |
117612 KB |
Output is correct |
4 |
Correct |
51 ms |
117680 KB |
Output is correct |
5 |
Correct |
53 ms |
117712 KB |
Output is correct |
6 |
Correct |
52 ms |
117648 KB |
Output is correct |
7 |
Correct |
52 ms |
117704 KB |
Output is correct |
8 |
Correct |
53 ms |
117732 KB |
Output is correct |
9 |
Correct |
53 ms |
117652 KB |
Output is correct |
10 |
Correct |
54 ms |
117640 KB |
Output is correct |
11 |
Correct |
52 ms |
117612 KB |
Output is correct |
12 |
Correct |
52 ms |
117732 KB |
Output is correct |
13 |
Correct |
52 ms |
117684 KB |
Output is correct |
14 |
Correct |
51 ms |
117640 KB |
Output is correct |
15 |
Correct |
54 ms |
117704 KB |
Output is correct |
16 |
Correct |
54 ms |
117708 KB |
Output is correct |
17 |
Correct |
54 ms |
117692 KB |
Output is correct |
18 |
Correct |
51 ms |
117680 KB |
Output is correct |
19 |
Correct |
53 ms |
117684 KB |
Output is correct |
20 |
Correct |
51 ms |
117716 KB |
Output is correct |
21 |
Correct |
51 ms |
117624 KB |
Output is correct |
22 |
Correct |
52 ms |
117708 KB |
Output is correct |
23 |
Correct |
52 ms |
117680 KB |
Output is correct |
24 |
Correct |
51 ms |
117640 KB |
Output is correct |
25 |
Correct |
66 ms |
118048 KB |
Output is correct |
26 |
Correct |
67 ms |
118220 KB |
Output is correct |
27 |
Correct |
66 ms |
118092 KB |
Output is correct |
28 |
Correct |
66 ms |
118368 KB |
Output is correct |
29 |
Correct |
67 ms |
118220 KB |
Output is correct |
30 |
Correct |
66 ms |
118236 KB |
Output is correct |
31 |
Correct |
65 ms |
118092 KB |
Output is correct |
32 |
Correct |
67 ms |
118056 KB |
Output is correct |
33 |
Correct |
66 ms |
117964 KB |
Output is correct |
34 |
Correct |
69 ms |
118012 KB |
Output is correct |
35 |
Correct |
63 ms |
117772 KB |
Output is correct |
36 |
Correct |
66 ms |
117708 KB |
Output is correct |
37 |
Correct |
96 ms |
135180 KB |
Output is correct |
38 |
Correct |
84 ms |
126552 KB |
Output is correct |
39 |
Correct |
65 ms |
117760 KB |
Output is correct |
40 |
Correct |
67 ms |
117756 KB |
Output is correct |
41 |
Correct |
84 ms |
125900 KB |
Output is correct |
42 |
Correct |
83 ms |
126012 KB |
Output is correct |
43 |
Correct |
66 ms |
117908 KB |
Output is correct |
44 |
Correct |
66 ms |
118040 KB |
Output is correct |
45 |
Execution timed out |
6051 ms |
125572 KB |
Time limit exceeded |
46 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
117648 KB |
Output is correct |
2 |
Correct |
50 ms |
117732 KB |
Output is correct |
3 |
Correct |
53 ms |
117612 KB |
Output is correct |
4 |
Correct |
51 ms |
117680 KB |
Output is correct |
5 |
Correct |
53 ms |
117712 KB |
Output is correct |
6 |
Correct |
52 ms |
117648 KB |
Output is correct |
7 |
Correct |
52 ms |
117704 KB |
Output is correct |
8 |
Correct |
53 ms |
117732 KB |
Output is correct |
9 |
Correct |
53 ms |
117652 KB |
Output is correct |
10 |
Correct |
54 ms |
117640 KB |
Output is correct |
11 |
Correct |
52 ms |
117612 KB |
Output is correct |
12 |
Correct |
52 ms |
117732 KB |
Output is correct |
13 |
Correct |
52 ms |
117684 KB |
Output is correct |
14 |
Correct |
51 ms |
117640 KB |
Output is correct |
15 |
Correct |
54 ms |
117704 KB |
Output is correct |
16 |
Correct |
54 ms |
117708 KB |
Output is correct |
17 |
Correct |
54 ms |
117692 KB |
Output is correct |
18 |
Correct |
51 ms |
117680 KB |
Output is correct |
19 |
Correct |
53 ms |
117684 KB |
Output is correct |
20 |
Correct |
51 ms |
117716 KB |
Output is correct |
21 |
Correct |
51 ms |
117624 KB |
Output is correct |
22 |
Correct |
52 ms |
117708 KB |
Output is correct |
23 |
Correct |
52 ms |
117680 KB |
Output is correct |
24 |
Correct |
51 ms |
117640 KB |
Output is correct |
25 |
Correct |
66 ms |
118048 KB |
Output is correct |
26 |
Correct |
67 ms |
118220 KB |
Output is correct |
27 |
Correct |
66 ms |
118092 KB |
Output is correct |
28 |
Correct |
66 ms |
118368 KB |
Output is correct |
29 |
Correct |
67 ms |
118220 KB |
Output is correct |
30 |
Correct |
66 ms |
118236 KB |
Output is correct |
31 |
Correct |
65 ms |
118092 KB |
Output is correct |
32 |
Correct |
67 ms |
118056 KB |
Output is correct |
33 |
Correct |
66 ms |
117964 KB |
Output is correct |
34 |
Correct |
69 ms |
118012 KB |
Output is correct |
35 |
Correct |
63 ms |
117772 KB |
Output is correct |
36 |
Correct |
66 ms |
117708 KB |
Output is correct |
37 |
Correct |
96 ms |
135180 KB |
Output is correct |
38 |
Correct |
84 ms |
126552 KB |
Output is correct |
39 |
Correct |
65 ms |
117760 KB |
Output is correct |
40 |
Correct |
67 ms |
117756 KB |
Output is correct |
41 |
Correct |
84 ms |
125900 KB |
Output is correct |
42 |
Correct |
83 ms |
126012 KB |
Output is correct |
43 |
Correct |
66 ms |
117908 KB |
Output is correct |
44 |
Correct |
66 ms |
118040 KB |
Output is correct |
45 |
Execution timed out |
6051 ms |
125572 KB |
Time limit exceeded |
46 |
Halted |
0 ms |
0 KB |
- |