#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mod = 1e9 + 7;
struct DisjointSet{
int n;
vector<int> par;
void Init(int _n) {
n = _n;
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int Find(int x) {
if (par[x] == x) return x;
return par[x] = Find(par[x]);
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
par[y] = x;
}
} dsu;
struct SegmentTree{
public:
int n;
vector<int> tree;
void Init(int _n) {
n = _n;
int sz = 1<<(Log2(n)+1);
tree.resize(sz);
fill(tree.begin(), tree.end(), -1);
}
void Update(int tar, int val) { Update(1, 1, n, tar, val); }
int Query(int l, int r) { return Query(1, 1, n, l, r); }
private:
static int Log2(int n) {
int ret = 0;
while (n > 1 << ret) ret ++;
return ret;
}
void Update(int node, int s, int e, int tar, int val) {
if (s > tar || tar > e) return;
if (s == e) {
tree[node] = val;
return;
}
int mid = s + e >> 1;
Update(node<<1, s, mid, tar, val);
Update(node<<1|1, mid+1, e, tar, val);
tree[node] = max(tree[node<<1], tree[node<<1|1]);
}
int Query(int node, int s, int e, int l, int r) {
if (l > e || s > r) return -1;
if (l <= s && e <= r) return tree[node];
int mid = s + e >> 1;
return max(Query(node<<1, s, mid, l, r), Query(node<<1|1, mid+1, e, l, r));
}
} seg;
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
vector<pii> a(n);
for (int i=0; i<n; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a.begin(), a.end());
seg.Init(2*n);
dsu.Init(2*n);
vector<int> chk(2*n, 0), nxt(2*n+1, -1);
for (int i=0; i<n; i++) {
if (i) {
for (int j=a[i-1].first+1; j<=a[i].first-1; j++) {
if (nxt[j] == -1) continue;
seg.Update(j, -1);
seg.Update(a[nxt[j]].second, nxt[j]);
}
}
vector<int> v;
while (true) {
int ret = seg.Query(a[i].first, a[i].second);
if (ret == -1) break;
v.push_back(ret);
seg.Update(a[ret].second, -1);
}
if (!v.empty()) {
sort(v.begin(), v.end(), [&] (int &u, int &v) { return a[u].first > a[v].first; });
for (auto &x : v) {
chk[dsu.Find(x<<1)] = 1;
if (chk[dsu.Find(x<<1)^1]) {
cout << "0\n";
return 0;
}
}
for (auto &x : v) chk[dsu.Find(x<<1)] = 0;
for (auto &x : v) {
dsu.Union(v[0]<<1, x<<1);
dsu.Union(v[0]<<1^1, x<<1^1);
}
dsu.Union(v[0]<<1^1, i<<1);
dsu.Union(v[0]<<1, i<<1^1);
for (int j=0; j<(int)v.size()-1; j++) {
nxt[a[v[j]].second] = v[j+1];
}
seg.Update(a[v[0]].second, v[0]);
}
seg.Update(a[i].second, i);
}
int ans = 1;
for (int i=0; i<n; i++) {
assert((dsu.Find(i<<1)^1) == dsu.Find(i<<1^1));
if (dsu.Find(i<<1) == (i<<1)) {
ans = ans * 2 % mod;
}
}
cout << ans << '\n';
}
Compilation message
port_facility.cpp: In member function 'void SegmentTree::Update(int, int, int, int, int)':
port_facility.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = s + e >> 1;
| ~~^~~
port_facility.cpp: In member function 'int SegmentTree::Query(int, int, int, int, int)':
port_facility.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = s + e >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
500 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
0 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
500 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
0 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
3 ms |
344 KB |
Output is correct |
26 |
Correct |
2 ms |
348 KB |
Output is correct |
27 |
Correct |
2 ms |
496 KB |
Output is correct |
28 |
Correct |
2 ms |
344 KB |
Output is correct |
29 |
Correct |
2 ms |
344 KB |
Output is correct |
30 |
Correct |
2 ms |
344 KB |
Output is correct |
31 |
Correct |
2 ms |
548 KB |
Output is correct |
32 |
Correct |
2 ms |
344 KB |
Output is correct |
33 |
Correct |
2 ms |
344 KB |
Output is correct |
34 |
Correct |
1 ms |
344 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
1 ms |
344 KB |
Output is correct |
39 |
Correct |
1 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
344 KB |
Output is correct |
41 |
Correct |
2 ms |
344 KB |
Output is correct |
42 |
Correct |
1 ms |
344 KB |
Output is correct |
43 |
Correct |
2 ms |
488 KB |
Output is correct |
44 |
Correct |
2 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
500 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
0 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
3 ms |
344 KB |
Output is correct |
26 |
Correct |
2 ms |
348 KB |
Output is correct |
27 |
Correct |
2 ms |
496 KB |
Output is correct |
28 |
Correct |
2 ms |
344 KB |
Output is correct |
29 |
Correct |
2 ms |
344 KB |
Output is correct |
30 |
Correct |
2 ms |
344 KB |
Output is correct |
31 |
Correct |
2 ms |
548 KB |
Output is correct |
32 |
Correct |
2 ms |
344 KB |
Output is correct |
33 |
Correct |
2 ms |
344 KB |
Output is correct |
34 |
Correct |
1 ms |
344 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
1 ms |
344 KB |
Output is correct |
39 |
Correct |
1 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
344 KB |
Output is correct |
41 |
Correct |
2 ms |
344 KB |
Output is correct |
42 |
Correct |
1 ms |
344 KB |
Output is correct |
43 |
Correct |
2 ms |
488 KB |
Output is correct |
44 |
Correct |
2 ms |
344 KB |
Output is correct |
45 |
Correct |
84 ms |
6224 KB |
Output is correct |
46 |
Correct |
85 ms |
6480 KB |
Output is correct |
47 |
Correct |
85 ms |
6224 KB |
Output is correct |
48 |
Correct |
86 ms |
6224 KB |
Output is correct |
49 |
Correct |
85 ms |
6480 KB |
Output is correct |
50 |
Correct |
33 ms |
6228 KB |
Output is correct |
51 |
Correct |
47 ms |
6480 KB |
Output is correct |
52 |
Correct |
39 ms |
6224 KB |
Output is correct |
53 |
Correct |
44 ms |
6228 KB |
Output is correct |
54 |
Correct |
20 ms |
6232 KB |
Output is correct |
55 |
Correct |
22 ms |
6224 KB |
Output is correct |
56 |
Correct |
22 ms |
6224 KB |
Output is correct |
57 |
Correct |
57 ms |
6228 KB |
Output is correct |
58 |
Correct |
41 ms |
6224 KB |
Output is correct |
59 |
Correct |
48 ms |
6412 KB |
Output is correct |
60 |
Correct |
65 ms |
6412 KB |
Output is correct |
61 |
Correct |
79 ms |
6544 KB |
Output is correct |
62 |
Correct |
22 ms |
6224 KB |
Output is correct |
63 |
Correct |
22 ms |
6224 KB |
Output is correct |
64 |
Correct |
22 ms |
6232 KB |
Output is correct |
65 |
Correct |
22 ms |
6224 KB |
Output is correct |
66 |
Correct |
21 ms |
6224 KB |
Output is correct |
67 |
Correct |
80 ms |
6736 KB |
Output is correct |
68 |
Correct |
79 ms |
7248 KB |
Output is correct |
69 |
Correct |
81 ms |
7484 KB |
Output is correct |
70 |
Correct |
81 ms |
7248 KB |
Output is correct |
71 |
Correct |
69 ms |
7248 KB |
Output is correct |
72 |
Correct |
68 ms |
7248 KB |
Output is correct |
73 |
Correct |
73 ms |
7252 KB |
Output is correct |
74 |
Correct |
75 ms |
7164 KB |
Output is correct |
75 |
Correct |
72 ms |
6736 KB |
Output is correct |
76 |
Correct |
72 ms |
6740 KB |
Output is correct |
77 |
Correct |
72 ms |
6856 KB |
Output is correct |
78 |
Correct |
84 ms |
6736 KB |
Output is correct |
79 |
Correct |
84 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
500 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
0 ms |
344 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
3 ms |
344 KB |
Output is correct |
26 |
Correct |
2 ms |
348 KB |
Output is correct |
27 |
Correct |
2 ms |
496 KB |
Output is correct |
28 |
Correct |
2 ms |
344 KB |
Output is correct |
29 |
Correct |
2 ms |
344 KB |
Output is correct |
30 |
Correct |
2 ms |
344 KB |
Output is correct |
31 |
Correct |
2 ms |
548 KB |
Output is correct |
32 |
Correct |
2 ms |
344 KB |
Output is correct |
33 |
Correct |
2 ms |
344 KB |
Output is correct |
34 |
Correct |
1 ms |
344 KB |
Output is correct |
35 |
Correct |
1 ms |
344 KB |
Output is correct |
36 |
Correct |
1 ms |
344 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
1 ms |
344 KB |
Output is correct |
39 |
Correct |
1 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
344 KB |
Output is correct |
41 |
Correct |
2 ms |
344 KB |
Output is correct |
42 |
Correct |
1 ms |
344 KB |
Output is correct |
43 |
Correct |
2 ms |
488 KB |
Output is correct |
44 |
Correct |
2 ms |
344 KB |
Output is correct |
45 |
Correct |
84 ms |
6224 KB |
Output is correct |
46 |
Correct |
85 ms |
6480 KB |
Output is correct |
47 |
Correct |
85 ms |
6224 KB |
Output is correct |
48 |
Correct |
86 ms |
6224 KB |
Output is correct |
49 |
Correct |
85 ms |
6480 KB |
Output is correct |
50 |
Correct |
33 ms |
6228 KB |
Output is correct |
51 |
Correct |
47 ms |
6480 KB |
Output is correct |
52 |
Correct |
39 ms |
6224 KB |
Output is correct |
53 |
Correct |
44 ms |
6228 KB |
Output is correct |
54 |
Correct |
20 ms |
6232 KB |
Output is correct |
55 |
Correct |
22 ms |
6224 KB |
Output is correct |
56 |
Correct |
22 ms |
6224 KB |
Output is correct |
57 |
Correct |
57 ms |
6228 KB |
Output is correct |
58 |
Correct |
41 ms |
6224 KB |
Output is correct |
59 |
Correct |
48 ms |
6412 KB |
Output is correct |
60 |
Correct |
65 ms |
6412 KB |
Output is correct |
61 |
Correct |
79 ms |
6544 KB |
Output is correct |
62 |
Correct |
22 ms |
6224 KB |
Output is correct |
63 |
Correct |
22 ms |
6224 KB |
Output is correct |
64 |
Correct |
22 ms |
6232 KB |
Output is correct |
65 |
Correct |
22 ms |
6224 KB |
Output is correct |
66 |
Correct |
21 ms |
6224 KB |
Output is correct |
67 |
Correct |
80 ms |
6736 KB |
Output is correct |
68 |
Correct |
79 ms |
7248 KB |
Output is correct |
69 |
Correct |
81 ms |
7484 KB |
Output is correct |
70 |
Correct |
81 ms |
7248 KB |
Output is correct |
71 |
Correct |
69 ms |
7248 KB |
Output is correct |
72 |
Correct |
68 ms |
7248 KB |
Output is correct |
73 |
Correct |
73 ms |
7252 KB |
Output is correct |
74 |
Correct |
75 ms |
7164 KB |
Output is correct |
75 |
Correct |
72 ms |
6736 KB |
Output is correct |
76 |
Correct |
72 ms |
6740 KB |
Output is correct |
77 |
Correct |
72 ms |
6856 KB |
Output is correct |
78 |
Correct |
84 ms |
6736 KB |
Output is correct |
79 |
Correct |
84 ms |
6744 KB |
Output is correct |
80 |
Correct |
929 ms |
62764 KB |
Output is correct |
81 |
Correct |
923 ms |
62768 KB |
Output is correct |
82 |
Correct |
922 ms |
62800 KB |
Output is correct |
83 |
Correct |
930 ms |
62928 KB |
Output is correct |
84 |
Correct |
924 ms |
62528 KB |
Output is correct |
85 |
Correct |
466 ms |
62544 KB |
Output is correct |
86 |
Correct |
561 ms |
62764 KB |
Output is correct |
87 |
Correct |
425 ms |
62936 KB |
Output is correct |
88 |
Correct |
491 ms |
62796 KB |
Output is correct |
89 |
Correct |
209 ms |
62544 KB |
Output is correct |
90 |
Correct |
222 ms |
62792 KB |
Output is correct |
91 |
Correct |
216 ms |
62540 KB |
Output is correct |
92 |
Correct |
632 ms |
62540 KB |
Output is correct |
93 |
Correct |
449 ms |
62556 KB |
Output is correct |
94 |
Correct |
576 ms |
62556 KB |
Output is correct |
95 |
Correct |
812 ms |
62668 KB |
Output is correct |
96 |
Correct |
899 ms |
62544 KB |
Output is correct |
97 |
Correct |
319 ms |
62544 KB |
Output is correct |
98 |
Correct |
453 ms |
62564 KB |
Output is correct |
99 |
Correct |
310 ms |
62796 KB |
Output is correct |
100 |
Correct |
216 ms |
62524 KB |
Output is correct |
101 |
Correct |
225 ms |
62664 KB |
Output is correct |
102 |
Correct |
902 ms |
64720 KB |
Output is correct |
103 |
Correct |
896 ms |
64848 KB |
Output is correct |
104 |
Correct |
892 ms |
64932 KB |
Output is correct |
105 |
Correct |
896 ms |
64716 KB |
Output is correct |
106 |
Correct |
763 ms |
65052 KB |
Output is correct |
107 |
Correct |
736 ms |
64976 KB |
Output is correct |
108 |
Correct |
791 ms |
65360 KB |
Output is correct |
109 |
Correct |
790 ms |
64736 KB |
Output is correct |
110 |
Correct |
788 ms |
62904 KB |
Output is correct |
111 |
Correct |
790 ms |
62764 KB |
Output is correct |
112 |
Correct |
787 ms |
62800 KB |
Output is correct |
113 |
Correct |
928 ms |
62772 KB |
Output is correct |
114 |
Correct |
928 ms |
62768 KB |
Output is correct |