#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
const int MOD = (int)1e9 + 7;
template<class T, class F = function<T(const T&, const T&)>>
struct SegmTree {
int n;
T def;
F f;
vector<T> t;
SegmTree(int n_, T def_, F f_) : n(n_), def(def_), f(f_), t(2 * n, def) {}
void Update(int pos, T val) {
t[pos += n] = val;
while (pos) {
pos /= 2;
t[pos] = f(t[2 * pos], t[2 * pos + 1]);
}
}
T Query(int l, int r) {
++r;
T ret = def;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) ret = f(ret, t[l++]);
if (r & 1) ret = f(ret, t[--r]);
}
return ret;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<pair<int, int>> v(n);
for (int i = 0; i < n; ++i) {
int x, y; cin >> x >> y; --x, --y;
v[i] = {x, y};
}
SegmTree<pair<int, int>> beg(2 * n, {2 * n, 2 * n},
[](pair<int, int> a, pair<int, int> b) {
return min(a, b);
});
SegmTree<pair<int, int>> fin(2 * n, {-1, -1},
[](pair<int, int> a, pair<int, int> b) {
return max(a, b);
});
for (int i = 0; i < n; ++i) {
fin.Update(v[i].first, {v[i].second, i});
beg.Update(v[i].second, {v[i].first, i});
}
vector<int> color(n, -1);
function<void(int, int)> DFS = [&](int node, int col) {
color[node] = col;
fin.Update(v[node].first, {-1, -1});
beg.Update(v[node].second, {2 * n, 2 * n});
while (true) {
auto p = fin.Query(v[node].first + 1, v[node].second - 1);
if (p.first < v[node].second) break;
DFS(p.second, 1 ^ col);
}
while (true) {
auto p = beg.Query(v[node].first + 1, v[node].second - 1);
if (p.first > v[node].first) break;
DFS(p.second, 1 ^ col);
}
};
int ans = 1;
for (int i = 0; i < n; ++i) {
if (color[i] == -1) {
ans += ans;
if (ans >= MOD) ans -= MOD;
DFS(i, 0);
}
}
vector<int> events(2 * n);
for (int i = 0; i < n; ++i) {
events[v[i].first] = i;
events[v[i].second] = ~i;
}
vector<vector<int>> stacks(2);
for (int node : events) {
auto &stk = stacks[color[node < 0 ? ~node : node]];
if (node >= 0) {
stk.emplace_back(node);
} else {
node = ~node;
if (!stk.empty() && stk.back() == node) stk.pop_back();
}
}
if (stacks[0].empty() && stacks[1].empty()) {
cout << ans << endl;
} else {
cout << 0 << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
8 ms |
640 KB |
Output is correct |
26 |
Correct |
8 ms |
640 KB |
Output is correct |
27 |
Correct |
8 ms |
640 KB |
Output is correct |
28 |
Correct |
8 ms |
640 KB |
Output is correct |
29 |
Correct |
8 ms |
640 KB |
Output is correct |
30 |
Correct |
7 ms |
640 KB |
Output is correct |
31 |
Correct |
7 ms |
640 KB |
Output is correct |
32 |
Correct |
8 ms |
640 KB |
Output is correct |
33 |
Correct |
7 ms |
512 KB |
Output is correct |
34 |
Correct |
8 ms |
640 KB |
Output is correct |
35 |
Correct |
7 ms |
512 KB |
Output is correct |
36 |
Correct |
7 ms |
512 KB |
Output is correct |
37 |
Correct |
8 ms |
768 KB |
Output is correct |
38 |
Correct |
8 ms |
640 KB |
Output is correct |
39 |
Correct |
8 ms |
512 KB |
Output is correct |
40 |
Correct |
7 ms |
512 KB |
Output is correct |
41 |
Correct |
8 ms |
768 KB |
Output is correct |
42 |
Correct |
7 ms |
768 KB |
Output is correct |
43 |
Correct |
8 ms |
768 KB |
Output is correct |
44 |
Correct |
8 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
8 ms |
640 KB |
Output is correct |
26 |
Correct |
8 ms |
640 KB |
Output is correct |
27 |
Correct |
8 ms |
640 KB |
Output is correct |
28 |
Correct |
8 ms |
640 KB |
Output is correct |
29 |
Correct |
8 ms |
640 KB |
Output is correct |
30 |
Correct |
7 ms |
640 KB |
Output is correct |
31 |
Correct |
7 ms |
640 KB |
Output is correct |
32 |
Correct |
8 ms |
640 KB |
Output is correct |
33 |
Correct |
7 ms |
512 KB |
Output is correct |
34 |
Correct |
8 ms |
640 KB |
Output is correct |
35 |
Correct |
7 ms |
512 KB |
Output is correct |
36 |
Correct |
7 ms |
512 KB |
Output is correct |
37 |
Correct |
8 ms |
768 KB |
Output is correct |
38 |
Correct |
8 ms |
640 KB |
Output is correct |
39 |
Correct |
8 ms |
512 KB |
Output is correct |
40 |
Correct |
7 ms |
512 KB |
Output is correct |
41 |
Correct |
8 ms |
768 KB |
Output is correct |
42 |
Correct |
7 ms |
768 KB |
Output is correct |
43 |
Correct |
8 ms |
768 KB |
Output is correct |
44 |
Correct |
8 ms |
768 KB |
Output is correct |
45 |
Correct |
213 ms |
10748 KB |
Output is correct |
46 |
Correct |
213 ms |
12408 KB |
Output is correct |
47 |
Correct |
206 ms |
9464 KB |
Output is correct |
48 |
Correct |
214 ms |
12408 KB |
Output is correct |
49 |
Correct |
207 ms |
9720 KB |
Output is correct |
50 |
Correct |
208 ms |
11976 KB |
Output is correct |
51 |
Correct |
206 ms |
12024 KB |
Output is correct |
52 |
Correct |
154 ms |
8696 KB |
Output is correct |
53 |
Correct |
198 ms |
9208 KB |
Output is correct |
54 |
Correct |
214 ms |
21752 KB |
Output is correct |
55 |
Correct |
220 ms |
15480 KB |
Output is correct |
56 |
Correct |
207 ms |
15352 KB |
Output is correct |
57 |
Correct |
165 ms |
8568 KB |
Output is correct |
58 |
Correct |
163 ms |
8568 KB |
Output is correct |
59 |
Correct |
190 ms |
8824 KB |
Output is correct |
60 |
Correct |
202 ms |
8872 KB |
Output is correct |
61 |
Correct |
200 ms |
8952 KB |
Output is correct |
62 |
Correct |
187 ms |
8824 KB |
Output is correct |
63 |
Correct |
198 ms |
8824 KB |
Output is correct |
64 |
Correct |
206 ms |
8824 KB |
Output is correct |
65 |
Correct |
281 ms |
21752 KB |
Output is correct |
66 |
Correct |
275 ms |
21748 KB |
Output is correct |
67 |
Correct |
233 ms |
15352 KB |
Output is correct |
68 |
Correct |
230 ms |
15480 KB |
Output is correct |
69 |
Correct |
228 ms |
14964 KB |
Output is correct |
70 |
Correct |
222 ms |
14836 KB |
Output is correct |
71 |
Correct |
225 ms |
21624 KB |
Output is correct |
72 |
Correct |
228 ms |
21816 KB |
Output is correct |
73 |
Correct |
216 ms |
17652 KB |
Output is correct |
74 |
Correct |
219 ms |
17668 KB |
Output is correct |
75 |
Correct |
160 ms |
15992 KB |
Output is correct |
76 |
Correct |
162 ms |
21112 KB |
Output is correct |
77 |
Correct |
167 ms |
21240 KB |
Output is correct |
78 |
Correct |
216 ms |
12024 KB |
Output is correct |
79 |
Correct |
218 ms |
10744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
8 ms |
640 KB |
Output is correct |
26 |
Correct |
8 ms |
640 KB |
Output is correct |
27 |
Correct |
8 ms |
640 KB |
Output is correct |
28 |
Correct |
8 ms |
640 KB |
Output is correct |
29 |
Correct |
8 ms |
640 KB |
Output is correct |
30 |
Correct |
7 ms |
640 KB |
Output is correct |
31 |
Correct |
7 ms |
640 KB |
Output is correct |
32 |
Correct |
8 ms |
640 KB |
Output is correct |
33 |
Correct |
7 ms |
512 KB |
Output is correct |
34 |
Correct |
8 ms |
640 KB |
Output is correct |
35 |
Correct |
7 ms |
512 KB |
Output is correct |
36 |
Correct |
7 ms |
512 KB |
Output is correct |
37 |
Correct |
8 ms |
768 KB |
Output is correct |
38 |
Correct |
8 ms |
640 KB |
Output is correct |
39 |
Correct |
8 ms |
512 KB |
Output is correct |
40 |
Correct |
7 ms |
512 KB |
Output is correct |
41 |
Correct |
8 ms |
768 KB |
Output is correct |
42 |
Correct |
7 ms |
768 KB |
Output is correct |
43 |
Correct |
8 ms |
768 KB |
Output is correct |
44 |
Correct |
8 ms |
768 KB |
Output is correct |
45 |
Correct |
213 ms |
10748 KB |
Output is correct |
46 |
Correct |
213 ms |
12408 KB |
Output is correct |
47 |
Correct |
206 ms |
9464 KB |
Output is correct |
48 |
Correct |
214 ms |
12408 KB |
Output is correct |
49 |
Correct |
207 ms |
9720 KB |
Output is correct |
50 |
Correct |
208 ms |
11976 KB |
Output is correct |
51 |
Correct |
206 ms |
12024 KB |
Output is correct |
52 |
Correct |
154 ms |
8696 KB |
Output is correct |
53 |
Correct |
198 ms |
9208 KB |
Output is correct |
54 |
Correct |
214 ms |
21752 KB |
Output is correct |
55 |
Correct |
220 ms |
15480 KB |
Output is correct |
56 |
Correct |
207 ms |
15352 KB |
Output is correct |
57 |
Correct |
165 ms |
8568 KB |
Output is correct |
58 |
Correct |
163 ms |
8568 KB |
Output is correct |
59 |
Correct |
190 ms |
8824 KB |
Output is correct |
60 |
Correct |
202 ms |
8872 KB |
Output is correct |
61 |
Correct |
200 ms |
8952 KB |
Output is correct |
62 |
Correct |
187 ms |
8824 KB |
Output is correct |
63 |
Correct |
198 ms |
8824 KB |
Output is correct |
64 |
Correct |
206 ms |
8824 KB |
Output is correct |
65 |
Correct |
281 ms |
21752 KB |
Output is correct |
66 |
Correct |
275 ms |
21748 KB |
Output is correct |
67 |
Correct |
233 ms |
15352 KB |
Output is correct |
68 |
Correct |
230 ms |
15480 KB |
Output is correct |
69 |
Correct |
228 ms |
14964 KB |
Output is correct |
70 |
Correct |
222 ms |
14836 KB |
Output is correct |
71 |
Correct |
225 ms |
21624 KB |
Output is correct |
72 |
Correct |
228 ms |
21816 KB |
Output is correct |
73 |
Correct |
216 ms |
17652 KB |
Output is correct |
74 |
Correct |
219 ms |
17668 KB |
Output is correct |
75 |
Correct |
160 ms |
15992 KB |
Output is correct |
76 |
Correct |
162 ms |
21112 KB |
Output is correct |
77 |
Correct |
167 ms |
21240 KB |
Output is correct |
78 |
Correct |
216 ms |
12024 KB |
Output is correct |
79 |
Correct |
218 ms |
10744 KB |
Output is correct |
80 |
Correct |
2882 ms |
92516 KB |
Output is correct |
81 |
Correct |
2749 ms |
91108 KB |
Output is correct |
82 |
Correct |
2669 ms |
86020 KB |
Output is correct |
83 |
Correct |
2716 ms |
91096 KB |
Output is correct |
84 |
Correct |
2837 ms |
92364 KB |
Output is correct |
85 |
Correct |
2701 ms |
86964 KB |
Output is correct |
86 |
Correct |
2658 ms |
91216 KB |
Output is correct |
87 |
Correct |
2334 ms |
82588 KB |
Output is correct |
88 |
Correct |
3172 ms |
86784 KB |
Output is correct |
89 |
Correct |
2842 ms |
213356 KB |
Output is correct |
90 |
Correct |
2945 ms |
149284 KB |
Output is correct |
91 |
Correct |
2828 ms |
149284 KB |
Output is correct |
92 |
Correct |
2342 ms |
82708 KB |
Output is correct |
93 |
Correct |
2325 ms |
82684 KB |
Output is correct |
94 |
Correct |
2938 ms |
85384 KB |
Output is correct |
95 |
Correct |
2724 ms |
84612 KB |
Output is correct |
96 |
Correct |
2732 ms |
84380 KB |
Output is correct |
97 |
Correct |
2766 ms |
85004 KB |
Output is correct |
98 |
Correct |
2697 ms |
84096 KB |
Output is correct |
99 |
Correct |
2644 ms |
86300 KB |
Output is correct |
100 |
Correct |
4072 ms |
212924 KB |
Output is correct |
101 |
Correct |
4161 ms |
226620 KB |
Output is correct |
102 |
Correct |
3045 ms |
164912 KB |
Output is correct |
103 |
Correct |
3014 ms |
164712 KB |
Output is correct |
104 |
Correct |
3041 ms |
158480 KB |
Output is correct |
105 |
Correct |
3052 ms |
158416 KB |
Output is correct |
106 |
Correct |
3033 ms |
227504 KB |
Output is correct |
107 |
Correct |
3081 ms |
227436 KB |
Output is correct |
108 |
Correct |
2900 ms |
186348 KB |
Output is correct |
109 |
Correct |
2917 ms |
186172 KB |
Output is correct |
110 |
Correct |
2190 ms |
220152 KB |
Output is correct |
111 |
Correct |
2254 ms |
222456 KB |
Output is correct |
112 |
Correct |
2279 ms |
222456 KB |
Output is correct |
113 |
Correct |
2695 ms |
100452 KB |
Output is correct |
114 |
Correct |
2706 ms |
105444 KB |
Output is correct |