#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e6;
const ll MOD = 1e9+7;
int N;
pii A[MAXN+10];
vector<int> adj[MAXN+10];
bool flag=true;
vector<int> tree[MAXN*4+10];
vector<int> memo;
void get(int node, int tl, int tr, int p, vector<int> &V)
{
if(!tree[node].empty()) memo.push_back(node);
for(auto it : tree[node]) V.push_back(it);
tree[node].clear();
if(tl==tr) return;
int mid=tl+tr>>1;
if(p<=mid) get(node*2, tl, mid, p, V);
else get(node*2+1, mid+1, tr, p, V);
}
void update(int node, int tl, int tr, int l, int r, int p)
{
if(l<=tl && tr<=r)
{
tree[node].push_back(p);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, p);
update(node*2+1, mid+1, tr, l, r, p);
}
struct UF
{
int par[MAXN+10], opp[MAXN+10];
void init()
{
for(int i=1; i<=N; i++)
{
par[i]=i;
opp[i]=-1;
}
}
int Find(int x)
{
if(x==par[x]) return par[x];
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
if(opp[x]==y) return;
if(x==y)
{
flag=false;
return;
}
int xt=opp[x], yt=opp[y];
if(yt!=-1) par[x]=yt;
if(xt!=-1) par[y]=xt;
x=par[x]; y=par[y];
opp[x]=y; opp[y]=x;
}
}uf;
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
sort(A+1, A+N+1, [&](const pii &p, const pii &q)
{
return p.second<q.second;
});
uf.init();
for(int i=1; i<=N; i++)
{
vector<int> V;
get(1, 1, 2*N, A[i].first, V);
for(auto it : V)
{
//printf("%d ", it);
uf.Union(i, it);
if(!flag) return !printf("0\n");
}
//printf(" : %d\n", i);
//for(int j=1; j<=N; j++) printf("%d -> %d %d\n", j, uf.par[j], uf.opp[j]);
int x=uf.Find(i), y=uf.opp[x];
update(1, 1, 2*N, A[i].first, A[i].second, x);
if(y!=-1) for(auto it : memo) tree[it].push_back(y);
memo.clear();
}
int sz=0;
for(int i=1; i<=N; i++)
{
if(uf.par[i]==i)
{
if(uf.opp[i]==-1) sz+=2;
else sz++;
}
}
sz/=2;
ll ans=1;
for(int i=1; i<=sz; i++)
{
ans*=2;
ans%=MOD;
}
printf("%lld\n", ans);
}
Compilation message
port_facility.cpp: In function 'void get(int, int, int, int, std::vector<int>&)':
port_facility.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
26 | int mid=tl+tr>>1;
| ~~^~~
port_facility.cpp: In function 'void update(int, int, int, int, int, int)':
port_facility.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid=tl+tr>>1;
| ~~^~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
port_facility.cpp:84:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | for(int i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
235108 KB |
Output is correct |
2 |
Correct |
139 ms |
235236 KB |
Output is correct |
3 |
Correct |
140 ms |
235108 KB |
Output is correct |
4 |
Correct |
146 ms |
235108 KB |
Output is correct |
5 |
Correct |
139 ms |
235220 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
136 ms |
235108 KB |
Output is correct |
8 |
Correct |
139 ms |
235108 KB |
Output is correct |
9 |
Correct |
136 ms |
235128 KB |
Output is correct |
10 |
Correct |
139 ms |
235108 KB |
Output is correct |
11 |
Correct |
135 ms |
235108 KB |
Output is correct |
12 |
Correct |
137 ms |
235236 KB |
Output is correct |
13 |
Correct |
135 ms |
235108 KB |
Output is correct |
14 |
Correct |
139 ms |
235108 KB |
Output is correct |
15 |
Correct |
139 ms |
235108 KB |
Output is correct |
16 |
Correct |
138 ms |
235108 KB |
Output is correct |
17 |
Correct |
138 ms |
235108 KB |
Output is correct |
18 |
Correct |
137 ms |
235108 KB |
Output is correct |
19 |
Correct |
143 ms |
235108 KB |
Output is correct |
20 |
Correct |
137 ms |
235108 KB |
Output is correct |
21 |
Correct |
136 ms |
235108 KB |
Output is correct |
22 |
Correct |
137 ms |
235108 KB |
Output is correct |
23 |
Correct |
136 ms |
235164 KB |
Output is correct |
24 |
Correct |
136 ms |
235208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
235108 KB |
Output is correct |
2 |
Correct |
139 ms |
235236 KB |
Output is correct |
3 |
Correct |
140 ms |
235108 KB |
Output is correct |
4 |
Correct |
146 ms |
235108 KB |
Output is correct |
5 |
Correct |
139 ms |
235220 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
136 ms |
235108 KB |
Output is correct |
8 |
Correct |
139 ms |
235108 KB |
Output is correct |
9 |
Correct |
136 ms |
235128 KB |
Output is correct |
10 |
Correct |
139 ms |
235108 KB |
Output is correct |
11 |
Correct |
135 ms |
235108 KB |
Output is correct |
12 |
Correct |
137 ms |
235236 KB |
Output is correct |
13 |
Correct |
135 ms |
235108 KB |
Output is correct |
14 |
Correct |
139 ms |
235108 KB |
Output is correct |
15 |
Correct |
139 ms |
235108 KB |
Output is correct |
16 |
Correct |
138 ms |
235108 KB |
Output is correct |
17 |
Correct |
138 ms |
235108 KB |
Output is correct |
18 |
Correct |
137 ms |
235108 KB |
Output is correct |
19 |
Correct |
143 ms |
235108 KB |
Output is correct |
20 |
Correct |
137 ms |
235108 KB |
Output is correct |
21 |
Correct |
136 ms |
235108 KB |
Output is correct |
22 |
Correct |
137 ms |
235108 KB |
Output is correct |
23 |
Correct |
136 ms |
235164 KB |
Output is correct |
24 |
Correct |
136 ms |
235208 KB |
Output is correct |
25 |
Correct |
138 ms |
235492 KB |
Output is correct |
26 |
Correct |
142 ms |
235364 KB |
Output is correct |
27 |
Correct |
140 ms |
235364 KB |
Output is correct |
28 |
Correct |
141 ms |
235364 KB |
Output is correct |
29 |
Correct |
137 ms |
235496 KB |
Output is correct |
30 |
Correct |
139 ms |
235492 KB |
Output is correct |
31 |
Correct |
138 ms |
235364 KB |
Output is correct |
32 |
Correct |
140 ms |
235364 KB |
Output is correct |
33 |
Correct |
137 ms |
235236 KB |
Output is correct |
34 |
Correct |
137 ms |
235240 KB |
Output is correct |
35 |
Correct |
138 ms |
235352 KB |
Output is correct |
36 |
Correct |
138 ms |
235364 KB |
Output is correct |
37 |
Correct |
137 ms |
235236 KB |
Output is correct |
38 |
Correct |
137 ms |
235236 KB |
Output is correct |
39 |
Correct |
138 ms |
235364 KB |
Output is correct |
40 |
Correct |
139 ms |
235364 KB |
Output is correct |
41 |
Correct |
139 ms |
235364 KB |
Output is correct |
42 |
Correct |
139 ms |
235368 KB |
Output is correct |
43 |
Correct |
139 ms |
235412 KB |
Output is correct |
44 |
Correct |
139 ms |
235364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
235108 KB |
Output is correct |
2 |
Correct |
139 ms |
235236 KB |
Output is correct |
3 |
Correct |
140 ms |
235108 KB |
Output is correct |
4 |
Correct |
146 ms |
235108 KB |
Output is correct |
5 |
Correct |
139 ms |
235220 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
136 ms |
235108 KB |
Output is correct |
8 |
Correct |
139 ms |
235108 KB |
Output is correct |
9 |
Correct |
136 ms |
235128 KB |
Output is correct |
10 |
Correct |
139 ms |
235108 KB |
Output is correct |
11 |
Correct |
135 ms |
235108 KB |
Output is correct |
12 |
Correct |
137 ms |
235236 KB |
Output is correct |
13 |
Correct |
135 ms |
235108 KB |
Output is correct |
14 |
Correct |
139 ms |
235108 KB |
Output is correct |
15 |
Correct |
139 ms |
235108 KB |
Output is correct |
16 |
Correct |
138 ms |
235108 KB |
Output is correct |
17 |
Correct |
138 ms |
235108 KB |
Output is correct |
18 |
Correct |
137 ms |
235108 KB |
Output is correct |
19 |
Correct |
143 ms |
235108 KB |
Output is correct |
20 |
Correct |
137 ms |
235108 KB |
Output is correct |
21 |
Correct |
136 ms |
235108 KB |
Output is correct |
22 |
Correct |
137 ms |
235108 KB |
Output is correct |
23 |
Correct |
136 ms |
235164 KB |
Output is correct |
24 |
Correct |
136 ms |
235208 KB |
Output is correct |
25 |
Correct |
138 ms |
235492 KB |
Output is correct |
26 |
Correct |
142 ms |
235364 KB |
Output is correct |
27 |
Correct |
140 ms |
235364 KB |
Output is correct |
28 |
Correct |
141 ms |
235364 KB |
Output is correct |
29 |
Correct |
137 ms |
235496 KB |
Output is correct |
30 |
Correct |
139 ms |
235492 KB |
Output is correct |
31 |
Correct |
138 ms |
235364 KB |
Output is correct |
32 |
Correct |
140 ms |
235364 KB |
Output is correct |
33 |
Correct |
137 ms |
235236 KB |
Output is correct |
34 |
Correct |
137 ms |
235240 KB |
Output is correct |
35 |
Correct |
138 ms |
235352 KB |
Output is correct |
36 |
Correct |
138 ms |
235364 KB |
Output is correct |
37 |
Correct |
137 ms |
235236 KB |
Output is correct |
38 |
Correct |
137 ms |
235236 KB |
Output is correct |
39 |
Correct |
138 ms |
235364 KB |
Output is correct |
40 |
Correct |
139 ms |
235364 KB |
Output is correct |
41 |
Correct |
139 ms |
235364 KB |
Output is correct |
42 |
Correct |
139 ms |
235368 KB |
Output is correct |
43 |
Correct |
139 ms |
235412 KB |
Output is correct |
44 |
Correct |
139 ms |
235364 KB |
Output is correct |
45 |
Correct |
280 ms |
246748 KB |
Output is correct |
46 |
Correct |
281 ms |
246620 KB |
Output is correct |
47 |
Correct |
288 ms |
246872 KB |
Output is correct |
48 |
Correct |
281 ms |
246620 KB |
Output is correct |
49 |
Correct |
284 ms |
246748 KB |
Output is correct |
50 |
Correct |
247 ms |
243684 KB |
Output is correct |
51 |
Correct |
189 ms |
238820 KB |
Output is correct |
52 |
Correct |
222 ms |
241892 KB |
Output is correct |
53 |
Correct |
272 ms |
249308 KB |
Output is correct |
54 |
Correct |
168 ms |
236772 KB |
Output is correct |
55 |
Correct |
165 ms |
236772 KB |
Output is correct |
56 |
Correct |
165 ms |
236772 KB |
Output is correct |
57 |
Correct |
227 ms |
242404 KB |
Output is correct |
58 |
Correct |
224 ms |
242424 KB |
Output is correct |
59 |
Correct |
257 ms |
245484 KB |
Output is correct |
60 |
Correct |
261 ms |
245732 KB |
Output is correct |
61 |
Correct |
283 ms |
245988 KB |
Output is correct |
62 |
Correct |
191 ms |
239076 KB |
Output is correct |
63 |
Correct |
231 ms |
242660 KB |
Output is correct |
64 |
Correct |
252 ms |
243812 KB |
Output is correct |
65 |
Correct |
167 ms |
236772 KB |
Output is correct |
66 |
Correct |
168 ms |
236900 KB |
Output is correct |
67 |
Correct |
309 ms |
250500 KB |
Output is correct |
68 |
Correct |
307 ms |
250112 KB |
Output is correct |
69 |
Correct |
309 ms |
250336 KB |
Output is correct |
70 |
Correct |
311 ms |
250592 KB |
Output is correct |
71 |
Correct |
281 ms |
249888 KB |
Output is correct |
72 |
Correct |
279 ms |
249372 KB |
Output is correct |
73 |
Correct |
288 ms |
249196 KB |
Output is correct |
74 |
Correct |
282 ms |
249192 KB |
Output is correct |
75 |
Correct |
233 ms |
244068 KB |
Output is correct |
76 |
Correct |
235 ms |
244068 KB |
Output is correct |
77 |
Correct |
232 ms |
244068 KB |
Output is correct |
78 |
Correct |
279 ms |
246620 KB |
Output is correct |
79 |
Correct |
278 ms |
246748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
136 ms |
235108 KB |
Output is correct |
2 |
Correct |
139 ms |
235236 KB |
Output is correct |
3 |
Correct |
140 ms |
235108 KB |
Output is correct |
4 |
Correct |
146 ms |
235108 KB |
Output is correct |
5 |
Correct |
139 ms |
235220 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
136 ms |
235108 KB |
Output is correct |
8 |
Correct |
139 ms |
235108 KB |
Output is correct |
9 |
Correct |
136 ms |
235128 KB |
Output is correct |
10 |
Correct |
139 ms |
235108 KB |
Output is correct |
11 |
Correct |
135 ms |
235108 KB |
Output is correct |
12 |
Correct |
137 ms |
235236 KB |
Output is correct |
13 |
Correct |
135 ms |
235108 KB |
Output is correct |
14 |
Correct |
139 ms |
235108 KB |
Output is correct |
15 |
Correct |
139 ms |
235108 KB |
Output is correct |
16 |
Correct |
138 ms |
235108 KB |
Output is correct |
17 |
Correct |
138 ms |
235108 KB |
Output is correct |
18 |
Correct |
137 ms |
235108 KB |
Output is correct |
19 |
Correct |
143 ms |
235108 KB |
Output is correct |
20 |
Correct |
137 ms |
235108 KB |
Output is correct |
21 |
Correct |
136 ms |
235108 KB |
Output is correct |
22 |
Correct |
137 ms |
235108 KB |
Output is correct |
23 |
Correct |
136 ms |
235164 KB |
Output is correct |
24 |
Correct |
136 ms |
235208 KB |
Output is correct |
25 |
Correct |
138 ms |
235492 KB |
Output is correct |
26 |
Correct |
142 ms |
235364 KB |
Output is correct |
27 |
Correct |
140 ms |
235364 KB |
Output is correct |
28 |
Correct |
141 ms |
235364 KB |
Output is correct |
29 |
Correct |
137 ms |
235496 KB |
Output is correct |
30 |
Correct |
139 ms |
235492 KB |
Output is correct |
31 |
Correct |
138 ms |
235364 KB |
Output is correct |
32 |
Correct |
140 ms |
235364 KB |
Output is correct |
33 |
Correct |
137 ms |
235236 KB |
Output is correct |
34 |
Correct |
137 ms |
235240 KB |
Output is correct |
35 |
Correct |
138 ms |
235352 KB |
Output is correct |
36 |
Correct |
138 ms |
235364 KB |
Output is correct |
37 |
Correct |
137 ms |
235236 KB |
Output is correct |
38 |
Correct |
137 ms |
235236 KB |
Output is correct |
39 |
Correct |
138 ms |
235364 KB |
Output is correct |
40 |
Correct |
139 ms |
235364 KB |
Output is correct |
41 |
Correct |
139 ms |
235364 KB |
Output is correct |
42 |
Correct |
139 ms |
235368 KB |
Output is correct |
43 |
Correct |
139 ms |
235412 KB |
Output is correct |
44 |
Correct |
139 ms |
235364 KB |
Output is correct |
45 |
Correct |
280 ms |
246748 KB |
Output is correct |
46 |
Correct |
281 ms |
246620 KB |
Output is correct |
47 |
Correct |
288 ms |
246872 KB |
Output is correct |
48 |
Correct |
281 ms |
246620 KB |
Output is correct |
49 |
Correct |
284 ms |
246748 KB |
Output is correct |
50 |
Correct |
247 ms |
243684 KB |
Output is correct |
51 |
Correct |
189 ms |
238820 KB |
Output is correct |
52 |
Correct |
222 ms |
241892 KB |
Output is correct |
53 |
Correct |
272 ms |
249308 KB |
Output is correct |
54 |
Correct |
168 ms |
236772 KB |
Output is correct |
55 |
Correct |
165 ms |
236772 KB |
Output is correct |
56 |
Correct |
165 ms |
236772 KB |
Output is correct |
57 |
Correct |
227 ms |
242404 KB |
Output is correct |
58 |
Correct |
224 ms |
242424 KB |
Output is correct |
59 |
Correct |
257 ms |
245484 KB |
Output is correct |
60 |
Correct |
261 ms |
245732 KB |
Output is correct |
61 |
Correct |
283 ms |
245988 KB |
Output is correct |
62 |
Correct |
191 ms |
239076 KB |
Output is correct |
63 |
Correct |
231 ms |
242660 KB |
Output is correct |
64 |
Correct |
252 ms |
243812 KB |
Output is correct |
65 |
Correct |
167 ms |
236772 KB |
Output is correct |
66 |
Correct |
168 ms |
236900 KB |
Output is correct |
67 |
Correct |
309 ms |
250500 KB |
Output is correct |
68 |
Correct |
307 ms |
250112 KB |
Output is correct |
69 |
Correct |
309 ms |
250336 KB |
Output is correct |
70 |
Correct |
311 ms |
250592 KB |
Output is correct |
71 |
Correct |
281 ms |
249888 KB |
Output is correct |
72 |
Correct |
279 ms |
249372 KB |
Output is correct |
73 |
Correct |
288 ms |
249196 KB |
Output is correct |
74 |
Correct |
282 ms |
249192 KB |
Output is correct |
75 |
Correct |
233 ms |
244068 KB |
Output is correct |
76 |
Correct |
235 ms |
244068 KB |
Output is correct |
77 |
Correct |
232 ms |
244068 KB |
Output is correct |
78 |
Correct |
279 ms |
246620 KB |
Output is correct |
79 |
Correct |
278 ms |
246748 KB |
Output is correct |
80 |
Correct |
1751 ms |
354628 KB |
Output is correct |
81 |
Correct |
1762 ms |
354488 KB |
Output is correct |
82 |
Correct |
1762 ms |
355784 KB |
Output is correct |
83 |
Correct |
1771 ms |
354372 KB |
Output is correct |
84 |
Correct |
1767 ms |
354636 KB |
Output is correct |
85 |
Correct |
985 ms |
289296 KB |
Output is correct |
86 |
Correct |
650 ms |
266440 KB |
Output is correct |
87 |
Correct |
1096 ms |
298596 KB |
Output is correct |
88 |
Correct |
1680 ms |
378460 KB |
Output is correct |
89 |
Correct |
461 ms |
250852 KB |
Output is correct |
90 |
Correct |
475 ms |
250852 KB |
Output is correct |
91 |
Correct |
481 ms |
250984 KB |
Output is correct |
92 |
Correct |
1155 ms |
306144 KB |
Output is correct |
93 |
Correct |
1127 ms |
302732 KB |
Output is correct |
94 |
Correct |
1555 ms |
341132 KB |
Output is correct |
95 |
Correct |
1653 ms |
345040 KB |
Output is correct |
96 |
Correct |
1690 ms |
346444 KB |
Output is correct |
97 |
Correct |
778 ms |
274916 KB |
Output is correct |
98 |
Correct |
713 ms |
271076 KB |
Output is correct |
99 |
Correct |
811 ms |
278244 KB |
Output is correct |
100 |
Correct |
468 ms |
250852 KB |
Output is correct |
101 |
Correct |
472 ms |
265444 KB |
Output is correct |
102 |
Correct |
2086 ms |
404444 KB |
Output is correct |
103 |
Correct |
2099 ms |
404600 KB |
Output is correct |
104 |
Correct |
2124 ms |
408240 KB |
Output is correct |
105 |
Correct |
2148 ms |
408128 KB |
Output is correct |
106 |
Correct |
1754 ms |
397220 KB |
Output is correct |
107 |
Correct |
1757 ms |
392996 KB |
Output is correct |
108 |
Correct |
1787 ms |
392208 KB |
Output is correct |
109 |
Correct |
1777 ms |
392204 KB |
Output is correct |
110 |
Correct |
1210 ms |
336228 KB |
Output is correct |
111 |
Correct |
1213 ms |
336480 KB |
Output is correct |
112 |
Correct |
1202 ms |
336356 KB |
Output is correct |
113 |
Correct |
1750 ms |
370040 KB |
Output is correct |
114 |
Correct |
1780 ms |
368968 KB |
Output is correct |