/*input
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12
3
1 4
2 5
3 6
5
1 4
2 10
6 9
7 8
3 5
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
vi rankas;
vi p;
vi edges[(int)1e6];
vpi poros;
vi kas;
int N;
int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j) {
edges[kas[i]].emplace_back(kas[j]);
edges[kas[j]].emplace_back(kas[i]);
if (isSameSet(i, j)) {
printf("0\n");
exit(0);
}
int x = findSet(i), y = findSet(j);
if (rankas[x] > rankas[y]) p[y] = x;
else {
p[x] = y;
if (rankas[x] == rankas[y]) rankas[y]++;
}
}
vb been(1e6, false);
vi keliai[2];
vi kitas;
void dfs(int x, int h) {
been[x] = true;
keliai[h].emplace_back(poros[x].x);
keliai[h].emplace_back(poros[x].y);
h = 1 - h;
for (auto u : edges[x])
if (!been[u])
dfs(u, h);
}
bool blogas() {
for (int n = 0; n < N; ++n)
{
if (been[n]) continue;
keliai[0].clear();
keliai[1].clear();
dfs(n, 0);
sort(keliai[0].begin(), keliai[0].end());
sort(keliai[1].begin(), keliai[1].end());
// printf("n = %d\n", n);
// print(keliai[0], "keliai[0]: ");
// print(keliai[1], "keliai[1]: ");
stack<int> stak;
for (auto u : keliai[0]) {
if (u < kitas[u]) stak.push(kitas[u]);
else {
if (stak.top() != u) return true;
stak.pop();
}
}
for (auto u : keliai[1]) {
if (u < kitas[u]) stak.push(kitas[u]);
else {
if (stak.top() != u) return true;
stak.pop();
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
p = vi(2 * N + 1); for (int i = 0; i <= 2 * N; i++) p[i] = i;
rankas = vi(2 * N + 1, 0);
kas = vi(2 * N + 1);
kitas = vi(2 * N + 1);
for (int i = 0; i < N; ++i)
{
int a, b;
cin >> a >> b;
kitas[a] = b;
kitas[b] = a;
unionSet(a, b);
kas[a] = kas[b] = i;
poros.emplace_back(a, b);
}
ll ats = 1;
// sort(poros.begin(), poros.end());
set<int> visos;
set<int> reikalingos;
for (int i = 1; i <= 2 * N; i++) {
if (i < kitas[i]) {
int a = i;
int b = kitas[i];
if (reikalingos.empty()) {
visos.insert(b);
reikalingos.insert(b);
continue;
}
auto it = reikalingos.begin();
int prad = *it;
if (b < prad) reikalingos.insert(b);
else {
while (it != reikalingos.end() and * it < b) {
// printf("jungiu i = %d, it = %d\n", i, *it);
unionSet(i, *it);
auto prev = it;
it = next(it);
reikalingos.erase(prev);
}
reikalingos.insert(prad);
}
visos.insert(b);
} else {
visos.erase(i);
reikalingos.erase(i);
if (visos.size())
reikalingos.insert(*visos.begin());
}
}
if (blogas()) {
printf("0\n");
return 0;
}
vb buvo(2 * N + 1, false);
for (int i = 1; i <= 2 * N; ++i)
{
if (!buvo[findSet(i)]) ats = (ats * 2) % MOD;
buvo[findSet(i)] = true;
}
printf("%lld\n", ats);
}
/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:180:8: warning: unused variable 'a' [-Wunused-variable]
int a = i;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
17 ms |
23936 KB |
Output is correct |
4 |
Correct |
17 ms |
23936 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
17 ms |
23936 KB |
Output is correct |
7 |
Correct |
17 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23936 KB |
Output is correct |
9 |
Correct |
17 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
18 ms |
23936 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
18 ms |
23936 KB |
Output is correct |
14 |
Correct |
17 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
18 ms |
23936 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
18 ms |
23936 KB |
Output is correct |
20 |
Correct |
18 ms |
23912 KB |
Output is correct |
21 |
Correct |
17 ms |
23936 KB |
Output is correct |
22 |
Correct |
18 ms |
23936 KB |
Output is correct |
23 |
Correct |
18 ms |
23936 KB |
Output is correct |
24 |
Correct |
17 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
17 ms |
23936 KB |
Output is correct |
4 |
Correct |
17 ms |
23936 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
17 ms |
23936 KB |
Output is correct |
7 |
Correct |
17 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23936 KB |
Output is correct |
9 |
Correct |
17 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
18 ms |
23936 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
18 ms |
23936 KB |
Output is correct |
14 |
Correct |
17 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
18 ms |
23936 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
18 ms |
23936 KB |
Output is correct |
20 |
Correct |
18 ms |
23912 KB |
Output is correct |
21 |
Correct |
17 ms |
23936 KB |
Output is correct |
22 |
Correct |
18 ms |
23936 KB |
Output is correct |
23 |
Correct |
18 ms |
23936 KB |
Output is correct |
24 |
Correct |
17 ms |
23936 KB |
Output is correct |
25 |
Correct |
19 ms |
24192 KB |
Output is correct |
26 |
Correct |
19 ms |
24148 KB |
Output is correct |
27 |
Correct |
19 ms |
24192 KB |
Output is correct |
28 |
Correct |
19 ms |
24192 KB |
Output is correct |
29 |
Correct |
19 ms |
24192 KB |
Output is correct |
30 |
Correct |
20 ms |
24192 KB |
Output is correct |
31 |
Correct |
19 ms |
24192 KB |
Output is correct |
32 |
Correct |
20 ms |
24192 KB |
Output is correct |
33 |
Correct |
19 ms |
24192 KB |
Output is correct |
34 |
Correct |
19 ms |
24184 KB |
Output is correct |
35 |
Correct |
19 ms |
24064 KB |
Output is correct |
36 |
Correct |
19 ms |
24192 KB |
Output is correct |
37 |
Correct |
19 ms |
24192 KB |
Output is correct |
38 |
Correct |
19 ms |
24192 KB |
Output is correct |
39 |
Correct |
19 ms |
24064 KB |
Output is correct |
40 |
Correct |
19 ms |
24064 KB |
Output is correct |
41 |
Correct |
20 ms |
24192 KB |
Output is correct |
42 |
Correct |
20 ms |
24320 KB |
Output is correct |
43 |
Correct |
19 ms |
24192 KB |
Output is correct |
44 |
Correct |
19 ms |
24192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
17 ms |
23936 KB |
Output is correct |
4 |
Correct |
17 ms |
23936 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
17 ms |
23936 KB |
Output is correct |
7 |
Correct |
17 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23936 KB |
Output is correct |
9 |
Correct |
17 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
18 ms |
23936 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
18 ms |
23936 KB |
Output is correct |
14 |
Correct |
17 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
18 ms |
23936 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
18 ms |
23936 KB |
Output is correct |
20 |
Correct |
18 ms |
23912 KB |
Output is correct |
21 |
Correct |
17 ms |
23936 KB |
Output is correct |
22 |
Correct |
18 ms |
23936 KB |
Output is correct |
23 |
Correct |
18 ms |
23936 KB |
Output is correct |
24 |
Correct |
17 ms |
23936 KB |
Output is correct |
25 |
Correct |
19 ms |
24192 KB |
Output is correct |
26 |
Correct |
19 ms |
24148 KB |
Output is correct |
27 |
Correct |
19 ms |
24192 KB |
Output is correct |
28 |
Correct |
19 ms |
24192 KB |
Output is correct |
29 |
Correct |
19 ms |
24192 KB |
Output is correct |
30 |
Correct |
20 ms |
24192 KB |
Output is correct |
31 |
Correct |
19 ms |
24192 KB |
Output is correct |
32 |
Correct |
20 ms |
24192 KB |
Output is correct |
33 |
Correct |
19 ms |
24192 KB |
Output is correct |
34 |
Correct |
19 ms |
24184 KB |
Output is correct |
35 |
Correct |
19 ms |
24064 KB |
Output is correct |
36 |
Correct |
19 ms |
24192 KB |
Output is correct |
37 |
Correct |
19 ms |
24192 KB |
Output is correct |
38 |
Correct |
19 ms |
24192 KB |
Output is correct |
39 |
Correct |
19 ms |
24064 KB |
Output is correct |
40 |
Correct |
19 ms |
24064 KB |
Output is correct |
41 |
Correct |
20 ms |
24192 KB |
Output is correct |
42 |
Correct |
20 ms |
24320 KB |
Output is correct |
43 |
Correct |
19 ms |
24192 KB |
Output is correct |
44 |
Correct |
19 ms |
24192 KB |
Output is correct |
45 |
Correct |
125 ms |
34916 KB |
Output is correct |
46 |
Correct |
130 ms |
35812 KB |
Output is correct |
47 |
Correct |
130 ms |
34788 KB |
Output is correct |
48 |
Correct |
128 ms |
35684 KB |
Output is correct |
49 |
Correct |
126 ms |
34916 KB |
Output is correct |
50 |
Correct |
111 ms |
35176 KB |
Output is correct |
51 |
Correct |
112 ms |
35300 KB |
Output is correct |
52 |
Correct |
84 ms |
30180 KB |
Output is correct |
53 |
Correct |
142 ms |
39268 KB |
Output is correct |
54 |
Correct |
124 ms |
39652 KB |
Output is correct |
55 |
Correct |
111 ms |
37092 KB |
Output is correct |
56 |
Correct |
117 ms |
37216 KB |
Output is correct |
57 |
Correct |
98 ms |
33124 KB |
Output is correct |
58 |
Correct |
87 ms |
30180 KB |
Output is correct |
59 |
Correct |
102 ms |
33384 KB |
Output is correct |
60 |
Correct |
119 ms |
33776 KB |
Output is correct |
61 |
Correct |
128 ms |
33636 KB |
Output is correct |
62 |
Correct |
97 ms |
33508 KB |
Output is correct |
63 |
Correct |
106 ms |
33892 KB |
Output is correct |
64 |
Correct |
109 ms |
33892 KB |
Output is correct |
65 |
Correct |
157 ms |
37348 KB |
Output is correct |
66 |
Correct |
156 ms |
37476 KB |
Output is correct |
67 |
Correct |
137 ms |
38116 KB |
Output is correct |
68 |
Correct |
145 ms |
38016 KB |
Output is correct |
69 |
Correct |
132 ms |
38372 KB |
Output is correct |
70 |
Correct |
130 ms |
38760 KB |
Output is correct |
71 |
Correct |
141 ms |
40164 KB |
Output is correct |
72 |
Correct |
146 ms |
40320 KB |
Output is correct |
73 |
Correct |
135 ms |
40292 KB |
Output is correct |
74 |
Correct |
136 ms |
40548 KB |
Output is correct |
75 |
Correct |
103 ms |
37092 KB |
Output is correct |
76 |
Correct |
114 ms |
36708 KB |
Output is correct |
77 |
Correct |
101 ms |
38328 KB |
Output is correct |
78 |
Correct |
126 ms |
35556 KB |
Output is correct |
79 |
Correct |
127 ms |
35172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
17 ms |
23936 KB |
Output is correct |
4 |
Correct |
17 ms |
23936 KB |
Output is correct |
5 |
Correct |
17 ms |
23936 KB |
Output is correct |
6 |
Correct |
17 ms |
23936 KB |
Output is correct |
7 |
Correct |
17 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23936 KB |
Output is correct |
9 |
Correct |
17 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
18 ms |
23936 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
18 ms |
23936 KB |
Output is correct |
14 |
Correct |
17 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
18 ms |
23936 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
18 ms |
23936 KB |
Output is correct |
20 |
Correct |
18 ms |
23912 KB |
Output is correct |
21 |
Correct |
17 ms |
23936 KB |
Output is correct |
22 |
Correct |
18 ms |
23936 KB |
Output is correct |
23 |
Correct |
18 ms |
23936 KB |
Output is correct |
24 |
Correct |
17 ms |
23936 KB |
Output is correct |
25 |
Correct |
19 ms |
24192 KB |
Output is correct |
26 |
Correct |
19 ms |
24148 KB |
Output is correct |
27 |
Correct |
19 ms |
24192 KB |
Output is correct |
28 |
Correct |
19 ms |
24192 KB |
Output is correct |
29 |
Correct |
19 ms |
24192 KB |
Output is correct |
30 |
Correct |
20 ms |
24192 KB |
Output is correct |
31 |
Correct |
19 ms |
24192 KB |
Output is correct |
32 |
Correct |
20 ms |
24192 KB |
Output is correct |
33 |
Correct |
19 ms |
24192 KB |
Output is correct |
34 |
Correct |
19 ms |
24184 KB |
Output is correct |
35 |
Correct |
19 ms |
24064 KB |
Output is correct |
36 |
Correct |
19 ms |
24192 KB |
Output is correct |
37 |
Correct |
19 ms |
24192 KB |
Output is correct |
38 |
Correct |
19 ms |
24192 KB |
Output is correct |
39 |
Correct |
19 ms |
24064 KB |
Output is correct |
40 |
Correct |
19 ms |
24064 KB |
Output is correct |
41 |
Correct |
20 ms |
24192 KB |
Output is correct |
42 |
Correct |
20 ms |
24320 KB |
Output is correct |
43 |
Correct |
19 ms |
24192 KB |
Output is correct |
44 |
Correct |
19 ms |
24192 KB |
Output is correct |
45 |
Correct |
125 ms |
34916 KB |
Output is correct |
46 |
Correct |
130 ms |
35812 KB |
Output is correct |
47 |
Correct |
130 ms |
34788 KB |
Output is correct |
48 |
Correct |
128 ms |
35684 KB |
Output is correct |
49 |
Correct |
126 ms |
34916 KB |
Output is correct |
50 |
Correct |
111 ms |
35176 KB |
Output is correct |
51 |
Correct |
112 ms |
35300 KB |
Output is correct |
52 |
Correct |
84 ms |
30180 KB |
Output is correct |
53 |
Correct |
142 ms |
39268 KB |
Output is correct |
54 |
Correct |
124 ms |
39652 KB |
Output is correct |
55 |
Correct |
111 ms |
37092 KB |
Output is correct |
56 |
Correct |
117 ms |
37216 KB |
Output is correct |
57 |
Correct |
98 ms |
33124 KB |
Output is correct |
58 |
Correct |
87 ms |
30180 KB |
Output is correct |
59 |
Correct |
102 ms |
33384 KB |
Output is correct |
60 |
Correct |
119 ms |
33776 KB |
Output is correct |
61 |
Correct |
128 ms |
33636 KB |
Output is correct |
62 |
Correct |
97 ms |
33508 KB |
Output is correct |
63 |
Correct |
106 ms |
33892 KB |
Output is correct |
64 |
Correct |
109 ms |
33892 KB |
Output is correct |
65 |
Correct |
157 ms |
37348 KB |
Output is correct |
66 |
Correct |
156 ms |
37476 KB |
Output is correct |
67 |
Correct |
137 ms |
38116 KB |
Output is correct |
68 |
Correct |
145 ms |
38016 KB |
Output is correct |
69 |
Correct |
132 ms |
38372 KB |
Output is correct |
70 |
Correct |
130 ms |
38760 KB |
Output is correct |
71 |
Correct |
141 ms |
40164 KB |
Output is correct |
72 |
Correct |
146 ms |
40320 KB |
Output is correct |
73 |
Correct |
135 ms |
40292 KB |
Output is correct |
74 |
Correct |
136 ms |
40548 KB |
Output is correct |
75 |
Correct |
103 ms |
37092 KB |
Output is correct |
76 |
Correct |
114 ms |
36708 KB |
Output is correct |
77 |
Correct |
101 ms |
38328 KB |
Output is correct |
78 |
Correct |
126 ms |
35556 KB |
Output is correct |
79 |
Correct |
127 ms |
35172 KB |
Output is correct |
80 |
Correct |
1696 ms |
134564 KB |
Output is correct |
81 |
Correct |
1689 ms |
133824 KB |
Output is correct |
82 |
Correct |
1660 ms |
132932 KB |
Output is correct |
83 |
Correct |
1645 ms |
133816 KB |
Output is correct |
84 |
Correct |
1686 ms |
134072 KB |
Output is correct |
85 |
Correct |
1530 ms |
133944 KB |
Output is correct |
86 |
Correct |
1545 ms |
136924 KB |
Output is correct |
87 |
Correct |
1033 ms |
85820 KB |
Output is correct |
88 |
Correct |
1963 ms |
179532 KB |
Output is correct |
89 |
Correct |
1724 ms |
180272 KB |
Output is correct |
90 |
Correct |
1637 ms |
156132 KB |
Output is correct |
91 |
Correct |
1585 ms |
156216 KB |
Output is correct |
92 |
Correct |
1333 ms |
117304 KB |
Output is correct |
93 |
Correct |
1039 ms |
86016 KB |
Output is correct |
94 |
Correct |
1450 ms |
122072 KB |
Output is correct |
95 |
Correct |
1650 ms |
122480 KB |
Output is correct |
96 |
Correct |
1643 ms |
120884 KB |
Output is correct |
97 |
Correct |
1354 ms |
122572 KB |
Output is correct |
98 |
Correct |
1553 ms |
123384 KB |
Output is correct |
99 |
Correct |
1555 ms |
127364 KB |
Output is correct |
100 |
Correct |
2820 ms |
159032 KB |
Output is correct |
101 |
Correct |
2872 ms |
159148 KB |
Output is correct |
102 |
Correct |
1961 ms |
162644 KB |
Output is correct |
103 |
Correct |
1926 ms |
162492 KB |
Output is correct |
104 |
Correct |
1925 ms |
169784 KB |
Output is correct |
105 |
Correct |
1910 ms |
169400 KB |
Output is correct |
106 |
Correct |
1925 ms |
191216 KB |
Output is correct |
107 |
Correct |
1955 ms |
191024 KB |
Output is correct |
108 |
Correct |
1885 ms |
191504 KB |
Output is correct |
109 |
Correct |
1978 ms |
191612 KB |
Output is correct |
110 |
Correct |
1425 ms |
176396 KB |
Output is correct |
111 |
Correct |
1413 ms |
173232 KB |
Output is correct |
112 |
Correct |
1383 ms |
165576 KB |
Output is correct |
113 |
Correct |
1710 ms |
132664 KB |
Output is correct |
114 |
Correct |
1681 ms |
133816 KB |
Output is correct |