#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
constexpr int maxn = 1e6+10, inf = 0x3f3f3f3f, mod = 1000000007;
struct SegmentTree
{
int base[maxn], tree[4*maxn], k;
SegmentTree(int _k) : k(_k) {}
inline int op(int a, int b) {return k?max(a,b):min(a,b);}
void build(int node, int i, int j) {
if(i == j) return (void)(tree[node] = base[i]?base[i]:(k?-inf:inf));
int m = (i+j) >> 1;
build(2*node, i, m); build(2*node+1, m+1, j);
tree[node] = op(tree[2*node], tree[2*node+1]);
}
void rm(int node, int i, int j, int pos) {
if(i == j) return (void)(tree[node] = k?-inf:inf);
int m = (i+j) >> 1;
if(pos <= m) rm(2*node, i, m, pos);
else rm(2*node+1, m+1, j, pos);
}
int find(int node, int i, int j, int l, int r, int val) {
if(i > r || j < l || (k && tree[node] < val) || (!k && tree[node] > val)) return -1;
if(i == j) return i;
int m = (i+j) >> 1;
if(k) {
int p1 = find(2*node, i, m, l, r, val);
if(p1 == -1) return find(2*node+1, m+1, j, l, r, val);
return p1;
} else {
int p1 = find(2*node+1, m+1, j, l, r, val);
if(p1 == -1) return find(2*node, i, m, l, r, val);
return p1;
}
}
} seg0(0), seg1(1);
pii a[maxn];
int pos[2*maxn], cor[maxn], mark[maxn], n;
void dfs(int i, int C) {
cor[i] = C;
mark[i] = 1;
seg0.rm(1, 1, 2*n, a[i].ss);
seg1.rm(1, 1, 2*n, a[i].ff);
int next;
while((next = seg1.find(1, 1, 2*n, a[i].ff+1, a[i].ss, a[i].ss)) != -1)
dfs(pos[next], !C);
while((next = seg0.find(1, 1, 2*n, a[i].ff, a[i].ss-1, a[i].ff)) != -1)
dfs(pos[next], !C);
}
int power(int b, int e) {
int ans = 1;
while(e) {
if(e&1) ans = (int)(1ll * ans * b % mod);
b = (int)(1ll * b * b % mod);
e >>= 1;
}
return ans;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d %d", &a[i].ff, &a[i].ss);
pos[a[i].ff] = i, pos[a[i].ss] = i;
seg1.base[a[i].ff] = a[i].ss, seg0.base[a[i].ss] = a[i].ff;
}
seg0.build(1, 1, 2*n);
seg1.build(1, 1, 2*n);
int cc = 0;
for(int i = 1; i <= n; i++)
if(!mark[i]) ++cc, dfs(i, 0);
vector<int> b, w, st;
for(int i = 1; i <= n; i++)
if(cor[i])
w.pb(a[i].ff), w.pb(a[i].ss);
else b.pb(a[i].ff), b.pb(a[i].ss);
sort(all(w)), sort(all(b));
int ok = 1;
for(int x : w)
if(st.size() && st.back() == pos[x])
st.pop_back();
else st.pb(pos[x]);
if(st.size()) ok = 0;
st.clear();
for(int x : b)
if(st.size() && st.back() == pos[x])
st.pop_back();
else st.pb(pos[x]);
if(st.size()) ok = 0;
printf("%d\n", ok?power(2, cc):0);
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
port_facility.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d %d", &a[i].ff, &a[i].ss);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
4 ms |
620 KB |
Output is correct |
26 |
Correct |
5 ms |
620 KB |
Output is correct |
27 |
Correct |
4 ms |
620 KB |
Output is correct |
28 |
Correct |
6 ms |
620 KB |
Output is correct |
29 |
Correct |
4 ms |
620 KB |
Output is correct |
30 |
Correct |
5 ms |
620 KB |
Output is correct |
31 |
Correct |
5 ms |
620 KB |
Output is correct |
32 |
Correct |
4 ms |
620 KB |
Output is correct |
33 |
Correct |
4 ms |
640 KB |
Output is correct |
34 |
Correct |
4 ms |
640 KB |
Output is correct |
35 |
Correct |
2 ms |
576 KB |
Output is correct |
36 |
Correct |
2 ms |
492 KB |
Output is correct |
37 |
Correct |
35 ms |
748 KB |
Output is correct |
38 |
Correct |
19 ms |
620 KB |
Output is correct |
39 |
Correct |
3 ms |
636 KB |
Output is correct |
40 |
Correct |
3 ms |
768 KB |
Output is correct |
41 |
Correct |
27 ms |
748 KB |
Output is correct |
42 |
Correct |
27 ms |
748 KB |
Output is correct |
43 |
Correct |
3 ms |
748 KB |
Output is correct |
44 |
Correct |
2 ms |
748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
4 ms |
620 KB |
Output is correct |
26 |
Correct |
5 ms |
620 KB |
Output is correct |
27 |
Correct |
4 ms |
620 KB |
Output is correct |
28 |
Correct |
6 ms |
620 KB |
Output is correct |
29 |
Correct |
4 ms |
620 KB |
Output is correct |
30 |
Correct |
5 ms |
620 KB |
Output is correct |
31 |
Correct |
5 ms |
620 KB |
Output is correct |
32 |
Correct |
4 ms |
620 KB |
Output is correct |
33 |
Correct |
4 ms |
640 KB |
Output is correct |
34 |
Correct |
4 ms |
640 KB |
Output is correct |
35 |
Correct |
2 ms |
576 KB |
Output is correct |
36 |
Correct |
2 ms |
492 KB |
Output is correct |
37 |
Correct |
35 ms |
748 KB |
Output is correct |
38 |
Correct |
19 ms |
620 KB |
Output is correct |
39 |
Correct |
3 ms |
636 KB |
Output is correct |
40 |
Correct |
3 ms |
768 KB |
Output is correct |
41 |
Correct |
27 ms |
748 KB |
Output is correct |
42 |
Correct |
27 ms |
748 KB |
Output is correct |
43 |
Correct |
3 ms |
748 KB |
Output is correct |
44 |
Correct |
2 ms |
748 KB |
Output is correct |
45 |
Correct |
322 ms |
12132 KB |
Output is correct |
46 |
Correct |
609 ms |
13412 KB |
Output is correct |
47 |
Correct |
232 ms |
11236 KB |
Output is correct |
48 |
Correct |
595 ms |
13412 KB |
Output is correct |
49 |
Correct |
267 ms |
11492 KB |
Output is correct |
50 |
Correct |
594 ms |
13028 KB |
Output is correct |
51 |
Correct |
343 ms |
13028 KB |
Output is correct |
52 |
Correct |
128 ms |
10852 KB |
Output is correct |
53 |
Correct |
113 ms |
10740 KB |
Output is correct |
54 |
Execution timed out |
6085 ms |
15724 KB |
Time limit exceeded |
55 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
4 ms |
620 KB |
Output is correct |
26 |
Correct |
5 ms |
620 KB |
Output is correct |
27 |
Correct |
4 ms |
620 KB |
Output is correct |
28 |
Correct |
6 ms |
620 KB |
Output is correct |
29 |
Correct |
4 ms |
620 KB |
Output is correct |
30 |
Correct |
5 ms |
620 KB |
Output is correct |
31 |
Correct |
5 ms |
620 KB |
Output is correct |
32 |
Correct |
4 ms |
620 KB |
Output is correct |
33 |
Correct |
4 ms |
640 KB |
Output is correct |
34 |
Correct |
4 ms |
640 KB |
Output is correct |
35 |
Correct |
2 ms |
576 KB |
Output is correct |
36 |
Correct |
2 ms |
492 KB |
Output is correct |
37 |
Correct |
35 ms |
748 KB |
Output is correct |
38 |
Correct |
19 ms |
620 KB |
Output is correct |
39 |
Correct |
3 ms |
636 KB |
Output is correct |
40 |
Correct |
3 ms |
768 KB |
Output is correct |
41 |
Correct |
27 ms |
748 KB |
Output is correct |
42 |
Correct |
27 ms |
748 KB |
Output is correct |
43 |
Correct |
3 ms |
748 KB |
Output is correct |
44 |
Correct |
2 ms |
748 KB |
Output is correct |
45 |
Correct |
322 ms |
12132 KB |
Output is correct |
46 |
Correct |
609 ms |
13412 KB |
Output is correct |
47 |
Correct |
232 ms |
11236 KB |
Output is correct |
48 |
Correct |
595 ms |
13412 KB |
Output is correct |
49 |
Correct |
267 ms |
11492 KB |
Output is correct |
50 |
Correct |
594 ms |
13028 KB |
Output is correct |
51 |
Correct |
343 ms |
13028 KB |
Output is correct |
52 |
Correct |
128 ms |
10852 KB |
Output is correct |
53 |
Correct |
113 ms |
10740 KB |
Output is correct |
54 |
Execution timed out |
6085 ms |
15724 KB |
Time limit exceeded |
55 |
Halted |
0 ms |
0 KB |
- |