#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
vector <pair <int, int>> s[3];
vector <int> adj[N];
pair <int, int> a[N];
int id[2 * N];
int c[N];
int nxt[N];
int par[N];
int n;
int getnxt(int u) {
return (nxt[u] == u || nxt[u] == 0) ? u : (nxt[u] = getnxt(nxt[u]));
}
int getpar(int u) {
return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}
bool join(int u, int v) {
u = getpar(u);
v = getpar(v);
if (u == v)
return false;
if (par[u] > par[v])
swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
void dfs(int u) {
for (int v : adj[u]) {
if (!c[v]) {
c[v] = 3 - c[u];
dfs(v);
} else if (c[u] == c[v]) {
cout << 0;
exit(0);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].fi >> a[i].se;
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
id[a[i].fi] = i;
id[a[i].se] = -i;
}
for (int i = 1, cur = 0; i <= 2 * n; i++) {
int u = abs(id[i]);
if (id[i] > 0) {
nxt[u] = u;
par[u] = -1;
cur = u;
} else {
int pos = u;
while (pos <= cur) {
int lo = pos;
int hi = n + 1;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
int nxtmid = getnxt(mid);
if (nxtmid <= cur && getpar(nxtmid) == getpar(u))
lo = mid;
else
hi = mid;
}
pos = getnxt(hi);
if (pos <= cur) {
adj[u].push_back(pos);
adj[pos].push_back(u);
assert(join(u, pos));
}
}
nxt[u] = u + 1;
}
}
for (int i = 1; i <= n; i++)
if (!c[i])
c[i] = 1, dfs(i);
for (int i = 1; i <= 2; i++)
s[i].push_back(mp(0, 2 * n + 1));
for (int i = 1; i <= 2 * n; i++) {
int u = abs(id[i]);
if (id[i] < 0)
s[c[u]].pop_back();
else {
if (a[u].se > s[c[u]].back().se)
return cout << 0, 0;
s[c[u]].push_back(a[u]);
}
}
int ans = 1;
for (int i = 1; i <= n; i++)
if (par[i] < 0)
ans = ans * 2 % mod;
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
18 ms |
23804 KB |
Output is correct |
3 |
Correct |
15 ms |
23752 KB |
Output is correct |
4 |
Correct |
18 ms |
23756 KB |
Output is correct |
5 |
Correct |
19 ms |
23768 KB |
Output is correct |
6 |
Correct |
17 ms |
23844 KB |
Output is correct |
7 |
Correct |
16 ms |
23784 KB |
Output is correct |
8 |
Correct |
17 ms |
23756 KB |
Output is correct |
9 |
Correct |
16 ms |
23792 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
15 ms |
23756 KB |
Output is correct |
12 |
Correct |
18 ms |
23756 KB |
Output is correct |
13 |
Correct |
18 ms |
23756 KB |
Output is correct |
14 |
Correct |
18 ms |
23756 KB |
Output is correct |
15 |
Correct |
17 ms |
23804 KB |
Output is correct |
16 |
Correct |
15 ms |
23808 KB |
Output is correct |
17 |
Correct |
19 ms |
23756 KB |
Output is correct |
18 |
Correct |
18 ms |
23756 KB |
Output is correct |
19 |
Correct |
17 ms |
23800 KB |
Output is correct |
20 |
Correct |
17 ms |
23736 KB |
Output is correct |
21 |
Correct |
15 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23812 KB |
Output is correct |
23 |
Correct |
19 ms |
23812 KB |
Output is correct |
24 |
Correct |
16 ms |
23736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
18 ms |
23804 KB |
Output is correct |
3 |
Correct |
15 ms |
23752 KB |
Output is correct |
4 |
Correct |
18 ms |
23756 KB |
Output is correct |
5 |
Correct |
19 ms |
23768 KB |
Output is correct |
6 |
Correct |
17 ms |
23844 KB |
Output is correct |
7 |
Correct |
16 ms |
23784 KB |
Output is correct |
8 |
Correct |
17 ms |
23756 KB |
Output is correct |
9 |
Correct |
16 ms |
23792 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
15 ms |
23756 KB |
Output is correct |
12 |
Correct |
18 ms |
23756 KB |
Output is correct |
13 |
Correct |
18 ms |
23756 KB |
Output is correct |
14 |
Correct |
18 ms |
23756 KB |
Output is correct |
15 |
Correct |
17 ms |
23804 KB |
Output is correct |
16 |
Correct |
15 ms |
23808 KB |
Output is correct |
17 |
Correct |
19 ms |
23756 KB |
Output is correct |
18 |
Correct |
18 ms |
23756 KB |
Output is correct |
19 |
Correct |
17 ms |
23800 KB |
Output is correct |
20 |
Correct |
17 ms |
23736 KB |
Output is correct |
21 |
Correct |
15 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23812 KB |
Output is correct |
23 |
Correct |
19 ms |
23812 KB |
Output is correct |
24 |
Correct |
16 ms |
23736 KB |
Output is correct |
25 |
Correct |
16 ms |
23964 KB |
Output is correct |
26 |
Correct |
19 ms |
23992 KB |
Output is correct |
27 |
Correct |
20 ms |
23992 KB |
Output is correct |
28 |
Correct |
16 ms |
23884 KB |
Output is correct |
29 |
Correct |
18 ms |
24012 KB |
Output is correct |
30 |
Correct |
19 ms |
23896 KB |
Output is correct |
31 |
Correct |
16 ms |
23884 KB |
Output is correct |
32 |
Correct |
18 ms |
24012 KB |
Output is correct |
33 |
Correct |
16 ms |
23884 KB |
Output is correct |
34 |
Correct |
19 ms |
23944 KB |
Output is correct |
35 |
Correct |
18 ms |
23824 KB |
Output is correct |
36 |
Correct |
18 ms |
23892 KB |
Output is correct |
37 |
Correct |
16 ms |
23980 KB |
Output is correct |
38 |
Correct |
17 ms |
23904 KB |
Output is correct |
39 |
Correct |
16 ms |
23948 KB |
Output is correct |
40 |
Correct |
16 ms |
23896 KB |
Output is correct |
41 |
Correct |
17 ms |
23884 KB |
Output is correct |
42 |
Correct |
19 ms |
23884 KB |
Output is correct |
43 |
Correct |
19 ms |
23952 KB |
Output is correct |
44 |
Correct |
17 ms |
24012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
18 ms |
23804 KB |
Output is correct |
3 |
Correct |
15 ms |
23752 KB |
Output is correct |
4 |
Correct |
18 ms |
23756 KB |
Output is correct |
5 |
Correct |
19 ms |
23768 KB |
Output is correct |
6 |
Correct |
17 ms |
23844 KB |
Output is correct |
7 |
Correct |
16 ms |
23784 KB |
Output is correct |
8 |
Correct |
17 ms |
23756 KB |
Output is correct |
9 |
Correct |
16 ms |
23792 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
15 ms |
23756 KB |
Output is correct |
12 |
Correct |
18 ms |
23756 KB |
Output is correct |
13 |
Correct |
18 ms |
23756 KB |
Output is correct |
14 |
Correct |
18 ms |
23756 KB |
Output is correct |
15 |
Correct |
17 ms |
23804 KB |
Output is correct |
16 |
Correct |
15 ms |
23808 KB |
Output is correct |
17 |
Correct |
19 ms |
23756 KB |
Output is correct |
18 |
Correct |
18 ms |
23756 KB |
Output is correct |
19 |
Correct |
17 ms |
23800 KB |
Output is correct |
20 |
Correct |
17 ms |
23736 KB |
Output is correct |
21 |
Correct |
15 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23812 KB |
Output is correct |
23 |
Correct |
19 ms |
23812 KB |
Output is correct |
24 |
Correct |
16 ms |
23736 KB |
Output is correct |
25 |
Correct |
16 ms |
23964 KB |
Output is correct |
26 |
Correct |
19 ms |
23992 KB |
Output is correct |
27 |
Correct |
20 ms |
23992 KB |
Output is correct |
28 |
Correct |
16 ms |
23884 KB |
Output is correct |
29 |
Correct |
18 ms |
24012 KB |
Output is correct |
30 |
Correct |
19 ms |
23896 KB |
Output is correct |
31 |
Correct |
16 ms |
23884 KB |
Output is correct |
32 |
Correct |
18 ms |
24012 KB |
Output is correct |
33 |
Correct |
16 ms |
23884 KB |
Output is correct |
34 |
Correct |
19 ms |
23944 KB |
Output is correct |
35 |
Correct |
18 ms |
23824 KB |
Output is correct |
36 |
Correct |
18 ms |
23892 KB |
Output is correct |
37 |
Correct |
16 ms |
23980 KB |
Output is correct |
38 |
Correct |
17 ms |
23904 KB |
Output is correct |
39 |
Correct |
16 ms |
23948 KB |
Output is correct |
40 |
Correct |
16 ms |
23896 KB |
Output is correct |
41 |
Correct |
17 ms |
23884 KB |
Output is correct |
42 |
Correct |
19 ms |
23884 KB |
Output is correct |
43 |
Correct |
19 ms |
23952 KB |
Output is correct |
44 |
Correct |
17 ms |
24012 KB |
Output is correct |
45 |
Correct |
89 ms |
31368 KB |
Output is correct |
46 |
Correct |
93 ms |
31612 KB |
Output is correct |
47 |
Correct |
99 ms |
31152 KB |
Output is correct |
48 |
Correct |
106 ms |
31636 KB |
Output is correct |
49 |
Correct |
108 ms |
31156 KB |
Output is correct |
50 |
Correct |
113 ms |
31140 KB |
Output is correct |
51 |
Correct |
86 ms |
31476 KB |
Output is correct |
52 |
Correct |
53 ms |
27828 KB |
Output is correct |
53 |
Correct |
68 ms |
28952 KB |
Output is correct |
54 |
Correct |
79 ms |
31324 KB |
Output is correct |
55 |
Correct |
75 ms |
31456 KB |
Output is correct |
56 |
Correct |
71 ms |
31296 KB |
Output is correct |
57 |
Correct |
69 ms |
30956 KB |
Output is correct |
58 |
Correct |
56 ms |
27780 KB |
Output is correct |
59 |
Correct |
72 ms |
28712 KB |
Output is correct |
60 |
Correct |
90 ms |
30184 KB |
Output is correct |
61 |
Correct |
94 ms |
30680 KB |
Output is correct |
62 |
Correct |
71 ms |
29408 KB |
Output is correct |
63 |
Correct |
78 ms |
29896 KB |
Output is correct |
64 |
Correct |
86 ms |
30272 KB |
Output is correct |
65 |
Correct |
91 ms |
31192 KB |
Output is correct |
66 |
Correct |
111 ms |
31284 KB |
Output is correct |
67 |
Correct |
93 ms |
32284 KB |
Output is correct |
68 |
Correct |
81 ms |
32296 KB |
Output is correct |
69 |
Correct |
84 ms |
32660 KB |
Output is correct |
70 |
Correct |
85 ms |
32648 KB |
Output is correct |
71 |
Correct |
78 ms |
32432 KB |
Output is correct |
72 |
Correct |
76 ms |
32424 KB |
Output is correct |
73 |
Correct |
76 ms |
32828 KB |
Output is correct |
74 |
Correct |
85 ms |
32804 KB |
Output is correct |
75 |
Correct |
86 ms |
35632 KB |
Output is correct |
76 |
Correct |
73 ms |
35608 KB |
Output is correct |
77 |
Correct |
80 ms |
35588 KB |
Output is correct |
78 |
Correct |
88 ms |
31544 KB |
Output is correct |
79 |
Correct |
92 ms |
31224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
18 ms |
23804 KB |
Output is correct |
3 |
Correct |
15 ms |
23752 KB |
Output is correct |
4 |
Correct |
18 ms |
23756 KB |
Output is correct |
5 |
Correct |
19 ms |
23768 KB |
Output is correct |
6 |
Correct |
17 ms |
23844 KB |
Output is correct |
7 |
Correct |
16 ms |
23784 KB |
Output is correct |
8 |
Correct |
17 ms |
23756 KB |
Output is correct |
9 |
Correct |
16 ms |
23792 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
15 ms |
23756 KB |
Output is correct |
12 |
Correct |
18 ms |
23756 KB |
Output is correct |
13 |
Correct |
18 ms |
23756 KB |
Output is correct |
14 |
Correct |
18 ms |
23756 KB |
Output is correct |
15 |
Correct |
17 ms |
23804 KB |
Output is correct |
16 |
Correct |
15 ms |
23808 KB |
Output is correct |
17 |
Correct |
19 ms |
23756 KB |
Output is correct |
18 |
Correct |
18 ms |
23756 KB |
Output is correct |
19 |
Correct |
17 ms |
23800 KB |
Output is correct |
20 |
Correct |
17 ms |
23736 KB |
Output is correct |
21 |
Correct |
15 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23812 KB |
Output is correct |
23 |
Correct |
19 ms |
23812 KB |
Output is correct |
24 |
Correct |
16 ms |
23736 KB |
Output is correct |
25 |
Correct |
16 ms |
23964 KB |
Output is correct |
26 |
Correct |
19 ms |
23992 KB |
Output is correct |
27 |
Correct |
20 ms |
23992 KB |
Output is correct |
28 |
Correct |
16 ms |
23884 KB |
Output is correct |
29 |
Correct |
18 ms |
24012 KB |
Output is correct |
30 |
Correct |
19 ms |
23896 KB |
Output is correct |
31 |
Correct |
16 ms |
23884 KB |
Output is correct |
32 |
Correct |
18 ms |
24012 KB |
Output is correct |
33 |
Correct |
16 ms |
23884 KB |
Output is correct |
34 |
Correct |
19 ms |
23944 KB |
Output is correct |
35 |
Correct |
18 ms |
23824 KB |
Output is correct |
36 |
Correct |
18 ms |
23892 KB |
Output is correct |
37 |
Correct |
16 ms |
23980 KB |
Output is correct |
38 |
Correct |
17 ms |
23904 KB |
Output is correct |
39 |
Correct |
16 ms |
23948 KB |
Output is correct |
40 |
Correct |
16 ms |
23896 KB |
Output is correct |
41 |
Correct |
17 ms |
23884 KB |
Output is correct |
42 |
Correct |
19 ms |
23884 KB |
Output is correct |
43 |
Correct |
19 ms |
23952 KB |
Output is correct |
44 |
Correct |
17 ms |
24012 KB |
Output is correct |
45 |
Correct |
89 ms |
31368 KB |
Output is correct |
46 |
Correct |
93 ms |
31612 KB |
Output is correct |
47 |
Correct |
99 ms |
31152 KB |
Output is correct |
48 |
Correct |
106 ms |
31636 KB |
Output is correct |
49 |
Correct |
108 ms |
31156 KB |
Output is correct |
50 |
Correct |
113 ms |
31140 KB |
Output is correct |
51 |
Correct |
86 ms |
31476 KB |
Output is correct |
52 |
Correct |
53 ms |
27828 KB |
Output is correct |
53 |
Correct |
68 ms |
28952 KB |
Output is correct |
54 |
Correct |
79 ms |
31324 KB |
Output is correct |
55 |
Correct |
75 ms |
31456 KB |
Output is correct |
56 |
Correct |
71 ms |
31296 KB |
Output is correct |
57 |
Correct |
69 ms |
30956 KB |
Output is correct |
58 |
Correct |
56 ms |
27780 KB |
Output is correct |
59 |
Correct |
72 ms |
28712 KB |
Output is correct |
60 |
Correct |
90 ms |
30184 KB |
Output is correct |
61 |
Correct |
94 ms |
30680 KB |
Output is correct |
62 |
Correct |
71 ms |
29408 KB |
Output is correct |
63 |
Correct |
78 ms |
29896 KB |
Output is correct |
64 |
Correct |
86 ms |
30272 KB |
Output is correct |
65 |
Correct |
91 ms |
31192 KB |
Output is correct |
66 |
Correct |
111 ms |
31284 KB |
Output is correct |
67 |
Correct |
93 ms |
32284 KB |
Output is correct |
68 |
Correct |
81 ms |
32296 KB |
Output is correct |
69 |
Correct |
84 ms |
32660 KB |
Output is correct |
70 |
Correct |
85 ms |
32648 KB |
Output is correct |
71 |
Correct |
78 ms |
32432 KB |
Output is correct |
72 |
Correct |
76 ms |
32424 KB |
Output is correct |
73 |
Correct |
76 ms |
32828 KB |
Output is correct |
74 |
Correct |
85 ms |
32804 KB |
Output is correct |
75 |
Correct |
86 ms |
35632 KB |
Output is correct |
76 |
Correct |
73 ms |
35608 KB |
Output is correct |
77 |
Correct |
80 ms |
35588 KB |
Output is correct |
78 |
Correct |
88 ms |
31544 KB |
Output is correct |
79 |
Correct |
92 ms |
31224 KB |
Output is correct |
80 |
Correct |
887 ms |
97336 KB |
Output is correct |
81 |
Correct |
872 ms |
96904 KB |
Output is correct |
82 |
Correct |
930 ms |
96096 KB |
Output is correct |
83 |
Correct |
909 ms |
97068 KB |
Output is correct |
84 |
Correct |
937 ms |
97336 KB |
Output is correct |
85 |
Correct |
992 ms |
95896 KB |
Output is correct |
86 |
Correct |
947 ms |
96436 KB |
Output is correct |
87 |
Correct |
439 ms |
65748 KB |
Output is correct |
88 |
Correct |
497 ms |
74084 KB |
Output is correct |
89 |
Correct |
691 ms |
101072 KB |
Output is correct |
90 |
Correct |
706 ms |
100952 KB |
Output is correct |
91 |
Correct |
741 ms |
100928 KB |
Output is correct |
92 |
Correct |
519 ms |
96976 KB |
Output is correct |
93 |
Correct |
486 ms |
65644 KB |
Output is correct |
94 |
Correct |
702 ms |
81008 KB |
Output is correct |
95 |
Correct |
820 ms |
92264 KB |
Output is correct |
96 |
Correct |
803 ms |
94704 KB |
Output is correct |
97 |
Correct |
659 ms |
83932 KB |
Output is correct |
98 |
Correct |
774 ms |
91948 KB |
Output is correct |
99 |
Correct |
902 ms |
94420 KB |
Output is correct |
100 |
Correct |
1196 ms |
100280 KB |
Output is correct |
101 |
Correct |
1281 ms |
99516 KB |
Output is correct |
102 |
Correct |
751 ms |
109648 KB |
Output is correct |
103 |
Correct |
796 ms |
109584 KB |
Output is correct |
104 |
Correct |
771 ms |
110740 KB |
Output is correct |
105 |
Correct |
676 ms |
110844 KB |
Output is correct |
106 |
Correct |
764 ms |
110952 KB |
Output is correct |
107 |
Correct |
843 ms |
111024 KB |
Output is correct |
108 |
Correct |
701 ms |
111900 KB |
Output is correct |
109 |
Correct |
781 ms |
111940 KB |
Output is correct |
110 |
Correct |
636 ms |
143912 KB |
Output is correct |
111 |
Correct |
656 ms |
143920 KB |
Output is correct |
112 |
Correct |
716 ms |
144036 KB |
Output is correct |
113 |
Correct |
879 ms |
96048 KB |
Output is correct |
114 |
Correct |
959 ms |
96956 KB |
Output is correct |