/*input
5
1 7
4 9
2 5
6 8
3 10
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
out<<'('<<P.F<<','<<P.S<<')';
return out;
}
//}}}
const ll maxn=1000005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;
ll mypow(ll a,ll b){
ll res=1LL;
while(b){
if(b&1) res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res;
}
int dsu[maxn];
int sz[maxn];
int mxout[maxn];
int a[maxn],b[maxn];
int find(int u){
if(dsu[u]==u) return u;
return dsu[u]=find(dsu[u]);
}
vector<int> edge[maxn];
void mrg(int u,int v){
int _u=u,_v=v;
u=find(u);
v=find(v);
if(u==v) return;
if(sz[u]<sz[v]) swap(u,v);
dsu[v]=u;
sz[u]+=sz[v];
if(b[mxout[u]]<b[mxout[v]]) mxout[u]=mxout[v];
edge[_u].pb(_v);
edge[_v].pb(_u);
// cout<<"mrg: "<<_u<<' '<<_v<<'\n';
}
vector<int> v;
pii tg[maxn*2];
bool type[maxn];
bool vis[maxn];
void dfs(int u){
vis[u]=1;
for(int v:edge[u]) if(!vis[v]){
type[v]=!type[u];
dfs(v);
}
}
vector<int> A,B;
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
IOS;
int n;
cin>>n;
REP(i,n) cin>>a[i]>>b[i];
REP(i,n) a[i]--,b[i]--;
REP(i,n) dsu[i]=i,sz[i]=1,mxout[i]=i;
REP(i,n) tg[a[i]]=MP(i,1);
REP(i,n) tg[b[i]]=MP(i,-1);
int cnt=0;
REP(i,n+n){
if(tg[i].S==1){
v.pb(tg[i].F);
}
else{
while(find(v.back())!=find(tg[i].F)){
mrg(tg[i].F,mxout[find(v.back())]);
v.pop_back();
}
if(i==b[mxout[find(tg[i].F)]]){
v.pop_back();
cnt++;
}
}
// for(int i:v) cout<<i<<' ';
// cout<<'\n';
// cout<<"dsu: \n";
// REP(i,n) cout<<find(i)<<' '<<mxout[find(i)]<<'\n';
}
REP(i,n) if(!vis[i]) dfs(i);
// REP(i,n) cout<<type[i]<<'\n';
REP(i,n+n){
if(tg[i].S==1){
if(type[tg[i].F]){
B.pb(tg[i].F);
}
else A.pb(tg[i].F);
}
else{
if(type[tg[i].F]){
if(B.back()!=tg[i].F){
cout<<"0\n";
return 0;
}
B.pop_back();
}
else{
if(A.back()!=tg[i].F){
cout<<"0\n";
return 0;
}
A.pop_back();
}
}
}
cout<<mypow(2,cnt)<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23800 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
30 ms |
23800 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
23 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23800 KB |
Output is correct |
10 |
Correct |
23 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
23 ms |
23800 KB |
Output is correct |
15 |
Correct |
23 ms |
23928 KB |
Output is correct |
16 |
Correct |
24 ms |
23928 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23928 KB |
Output is correct |
19 |
Correct |
23 ms |
23928 KB |
Output is correct |
20 |
Correct |
24 ms |
23928 KB |
Output is correct |
21 |
Correct |
23 ms |
23928 KB |
Output is correct |
22 |
Correct |
24 ms |
23800 KB |
Output is correct |
23 |
Correct |
29 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23800 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
30 ms |
23800 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
23 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23800 KB |
Output is correct |
10 |
Correct |
23 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
23 ms |
23800 KB |
Output is correct |
15 |
Correct |
23 ms |
23928 KB |
Output is correct |
16 |
Correct |
24 ms |
23928 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23928 KB |
Output is correct |
19 |
Correct |
23 ms |
23928 KB |
Output is correct |
20 |
Correct |
24 ms |
23928 KB |
Output is correct |
21 |
Correct |
23 ms |
23928 KB |
Output is correct |
22 |
Correct |
24 ms |
23800 KB |
Output is correct |
23 |
Correct |
29 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23928 KB |
Output is correct |
25 |
Correct |
25 ms |
24056 KB |
Output is correct |
26 |
Correct |
25 ms |
24056 KB |
Output is correct |
27 |
Correct |
25 ms |
24056 KB |
Output is correct |
28 |
Correct |
29 ms |
24056 KB |
Output is correct |
29 |
Correct |
24 ms |
24056 KB |
Output is correct |
30 |
Correct |
25 ms |
24056 KB |
Output is correct |
31 |
Correct |
25 ms |
24056 KB |
Output is correct |
32 |
Correct |
33 ms |
24056 KB |
Output is correct |
33 |
Correct |
25 ms |
24060 KB |
Output is correct |
34 |
Correct |
24 ms |
24060 KB |
Output is correct |
35 |
Correct |
24 ms |
23928 KB |
Output is correct |
36 |
Correct |
29 ms |
23932 KB |
Output is correct |
37 |
Correct |
28 ms |
24056 KB |
Output is correct |
38 |
Correct |
25 ms |
24080 KB |
Output is correct |
39 |
Correct |
24 ms |
24000 KB |
Output is correct |
40 |
Correct |
24 ms |
23928 KB |
Output is correct |
41 |
Correct |
25 ms |
24056 KB |
Output is correct |
42 |
Correct |
28 ms |
24056 KB |
Output is correct |
43 |
Correct |
24 ms |
24056 KB |
Output is correct |
44 |
Correct |
24 ms |
24056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23800 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
30 ms |
23800 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
23 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23800 KB |
Output is correct |
10 |
Correct |
23 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
23 ms |
23800 KB |
Output is correct |
15 |
Correct |
23 ms |
23928 KB |
Output is correct |
16 |
Correct |
24 ms |
23928 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23928 KB |
Output is correct |
19 |
Correct |
23 ms |
23928 KB |
Output is correct |
20 |
Correct |
24 ms |
23928 KB |
Output is correct |
21 |
Correct |
23 ms |
23928 KB |
Output is correct |
22 |
Correct |
24 ms |
23800 KB |
Output is correct |
23 |
Correct |
29 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23928 KB |
Output is correct |
25 |
Correct |
25 ms |
24056 KB |
Output is correct |
26 |
Correct |
25 ms |
24056 KB |
Output is correct |
27 |
Correct |
25 ms |
24056 KB |
Output is correct |
28 |
Correct |
29 ms |
24056 KB |
Output is correct |
29 |
Correct |
24 ms |
24056 KB |
Output is correct |
30 |
Correct |
25 ms |
24056 KB |
Output is correct |
31 |
Correct |
25 ms |
24056 KB |
Output is correct |
32 |
Correct |
33 ms |
24056 KB |
Output is correct |
33 |
Correct |
25 ms |
24060 KB |
Output is correct |
34 |
Correct |
24 ms |
24060 KB |
Output is correct |
35 |
Correct |
24 ms |
23928 KB |
Output is correct |
36 |
Correct |
29 ms |
23932 KB |
Output is correct |
37 |
Correct |
28 ms |
24056 KB |
Output is correct |
38 |
Correct |
25 ms |
24080 KB |
Output is correct |
39 |
Correct |
24 ms |
24000 KB |
Output is correct |
40 |
Correct |
24 ms |
23928 KB |
Output is correct |
41 |
Correct |
25 ms |
24056 KB |
Output is correct |
42 |
Correct |
28 ms |
24056 KB |
Output is correct |
43 |
Correct |
24 ms |
24056 KB |
Output is correct |
44 |
Correct |
24 ms |
24056 KB |
Output is correct |
45 |
Correct |
90 ms |
32144 KB |
Output is correct |
46 |
Correct |
93 ms |
32412 KB |
Output is correct |
47 |
Correct |
87 ms |
31968 KB |
Output is correct |
48 |
Correct |
89 ms |
32504 KB |
Output is correct |
49 |
Correct |
89 ms |
32120 KB |
Output is correct |
50 |
Correct |
87 ms |
32228 KB |
Output is correct |
51 |
Correct |
85 ms |
32500 KB |
Output is correct |
52 |
Correct |
55 ms |
28676 KB |
Output is correct |
53 |
Correct |
53 ms |
29940 KB |
Output is correct |
54 |
Correct |
82 ms |
33592 KB |
Output is correct |
55 |
Correct |
78 ms |
33012 KB |
Output is correct |
56 |
Correct |
84 ms |
33032 KB |
Output is correct |
57 |
Correct |
79 ms |
31992 KB |
Output is correct |
58 |
Correct |
55 ms |
28792 KB |
Output is correct |
59 |
Correct |
60 ms |
29684 KB |
Output is correct |
60 |
Correct |
76 ms |
31096 KB |
Output is correct |
61 |
Correct |
87 ms |
31728 KB |
Output is correct |
62 |
Correct |
67 ms |
30836 KB |
Output is correct |
63 |
Correct |
76 ms |
31224 KB |
Output is correct |
64 |
Correct |
86 ms |
31608 KB |
Output is correct |
65 |
Correct |
91 ms |
32888 KB |
Output is correct |
66 |
Correct |
90 ms |
32876 KB |
Output is correct |
67 |
Correct |
83 ms |
33140 KB |
Output is correct |
68 |
Correct |
81 ms |
33016 KB |
Output is correct |
69 |
Correct |
85 ms |
33140 KB |
Output is correct |
70 |
Correct |
85 ms |
33224 KB |
Output is correct |
71 |
Correct |
78 ms |
33396 KB |
Output is correct |
72 |
Correct |
77 ms |
33456 KB |
Output is correct |
73 |
Correct |
80 ms |
33780 KB |
Output is correct |
74 |
Correct |
83 ms |
33908 KB |
Output is correct |
75 |
Correct |
88 ms |
34808 KB |
Output is correct |
76 |
Correct |
88 ms |
34424 KB |
Output is correct |
77 |
Correct |
93 ms |
35832 KB |
Output is correct |
78 |
Correct |
95 ms |
32404 KB |
Output is correct |
79 |
Correct |
88 ms |
32376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23928 KB |
Output is correct |
3 |
Correct |
23 ms |
23800 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
30 ms |
23800 KB |
Output is correct |
6 |
Correct |
23 ms |
23800 KB |
Output is correct |
7 |
Correct |
23 ms |
23800 KB |
Output is correct |
8 |
Correct |
23 ms |
23800 KB |
Output is correct |
9 |
Correct |
23 ms |
23800 KB |
Output is correct |
10 |
Correct |
23 ms |
23800 KB |
Output is correct |
11 |
Correct |
23 ms |
23928 KB |
Output is correct |
12 |
Correct |
23 ms |
23800 KB |
Output is correct |
13 |
Correct |
23 ms |
23800 KB |
Output is correct |
14 |
Correct |
23 ms |
23800 KB |
Output is correct |
15 |
Correct |
23 ms |
23928 KB |
Output is correct |
16 |
Correct |
24 ms |
23928 KB |
Output is correct |
17 |
Correct |
23 ms |
23928 KB |
Output is correct |
18 |
Correct |
23 ms |
23928 KB |
Output is correct |
19 |
Correct |
23 ms |
23928 KB |
Output is correct |
20 |
Correct |
24 ms |
23928 KB |
Output is correct |
21 |
Correct |
23 ms |
23928 KB |
Output is correct |
22 |
Correct |
24 ms |
23800 KB |
Output is correct |
23 |
Correct |
29 ms |
23800 KB |
Output is correct |
24 |
Correct |
23 ms |
23928 KB |
Output is correct |
25 |
Correct |
25 ms |
24056 KB |
Output is correct |
26 |
Correct |
25 ms |
24056 KB |
Output is correct |
27 |
Correct |
25 ms |
24056 KB |
Output is correct |
28 |
Correct |
29 ms |
24056 KB |
Output is correct |
29 |
Correct |
24 ms |
24056 KB |
Output is correct |
30 |
Correct |
25 ms |
24056 KB |
Output is correct |
31 |
Correct |
25 ms |
24056 KB |
Output is correct |
32 |
Correct |
33 ms |
24056 KB |
Output is correct |
33 |
Correct |
25 ms |
24060 KB |
Output is correct |
34 |
Correct |
24 ms |
24060 KB |
Output is correct |
35 |
Correct |
24 ms |
23928 KB |
Output is correct |
36 |
Correct |
29 ms |
23932 KB |
Output is correct |
37 |
Correct |
28 ms |
24056 KB |
Output is correct |
38 |
Correct |
25 ms |
24080 KB |
Output is correct |
39 |
Correct |
24 ms |
24000 KB |
Output is correct |
40 |
Correct |
24 ms |
23928 KB |
Output is correct |
41 |
Correct |
25 ms |
24056 KB |
Output is correct |
42 |
Correct |
28 ms |
24056 KB |
Output is correct |
43 |
Correct |
24 ms |
24056 KB |
Output is correct |
44 |
Correct |
24 ms |
24056 KB |
Output is correct |
45 |
Correct |
90 ms |
32144 KB |
Output is correct |
46 |
Correct |
93 ms |
32412 KB |
Output is correct |
47 |
Correct |
87 ms |
31968 KB |
Output is correct |
48 |
Correct |
89 ms |
32504 KB |
Output is correct |
49 |
Correct |
89 ms |
32120 KB |
Output is correct |
50 |
Correct |
87 ms |
32228 KB |
Output is correct |
51 |
Correct |
85 ms |
32500 KB |
Output is correct |
52 |
Correct |
55 ms |
28676 KB |
Output is correct |
53 |
Correct |
53 ms |
29940 KB |
Output is correct |
54 |
Correct |
82 ms |
33592 KB |
Output is correct |
55 |
Correct |
78 ms |
33012 KB |
Output is correct |
56 |
Correct |
84 ms |
33032 KB |
Output is correct |
57 |
Correct |
79 ms |
31992 KB |
Output is correct |
58 |
Correct |
55 ms |
28792 KB |
Output is correct |
59 |
Correct |
60 ms |
29684 KB |
Output is correct |
60 |
Correct |
76 ms |
31096 KB |
Output is correct |
61 |
Correct |
87 ms |
31728 KB |
Output is correct |
62 |
Correct |
67 ms |
30836 KB |
Output is correct |
63 |
Correct |
76 ms |
31224 KB |
Output is correct |
64 |
Correct |
86 ms |
31608 KB |
Output is correct |
65 |
Correct |
91 ms |
32888 KB |
Output is correct |
66 |
Correct |
90 ms |
32876 KB |
Output is correct |
67 |
Correct |
83 ms |
33140 KB |
Output is correct |
68 |
Correct |
81 ms |
33016 KB |
Output is correct |
69 |
Correct |
85 ms |
33140 KB |
Output is correct |
70 |
Correct |
85 ms |
33224 KB |
Output is correct |
71 |
Correct |
78 ms |
33396 KB |
Output is correct |
72 |
Correct |
77 ms |
33456 KB |
Output is correct |
73 |
Correct |
80 ms |
33780 KB |
Output is correct |
74 |
Correct |
83 ms |
33908 KB |
Output is correct |
75 |
Correct |
88 ms |
34808 KB |
Output is correct |
76 |
Correct |
88 ms |
34424 KB |
Output is correct |
77 |
Correct |
93 ms |
35832 KB |
Output is correct |
78 |
Correct |
95 ms |
32404 KB |
Output is correct |
79 |
Correct |
88 ms |
32376 KB |
Output is correct |
80 |
Correct |
1047 ms |
95788 KB |
Output is correct |
81 |
Correct |
1056 ms |
95480 KB |
Output is correct |
82 |
Correct |
1059 ms |
95428 KB |
Output is correct |
83 |
Correct |
1048 ms |
96120 KB |
Output is correct |
84 |
Correct |
1020 ms |
96628 KB |
Output is correct |
85 |
Correct |
1113 ms |
96684 KB |
Output is correct |
86 |
Correct |
1114 ms |
97220 KB |
Output is correct |
87 |
Correct |
379 ms |
62804 KB |
Output is correct |
88 |
Correct |
355 ms |
72900 KB |
Output is correct |
89 |
Correct |
1035 ms |
109088 KB |
Output is correct |
90 |
Correct |
979 ms |
104292 KB |
Output is correct |
91 |
Correct |
994 ms |
104148 KB |
Output is correct |
92 |
Correct |
984 ms |
95224 KB |
Output is correct |
93 |
Correct |
399 ms |
62712 KB |
Output is correct |
94 |
Correct |
658 ms |
79724 KB |
Output is correct |
95 |
Correct |
988 ms |
90856 KB |
Output is correct |
96 |
Correct |
1025 ms |
92952 KB |
Output is correct |
97 |
Correct |
830 ms |
82408 KB |
Output is correct |
98 |
Correct |
1084 ms |
90392 KB |
Output is correct |
99 |
Correct |
1096 ms |
94100 KB |
Output is correct |
100 |
Correct |
1233 ms |
103768 KB |
Output is correct |
101 |
Correct |
1242 ms |
103016 KB |
Output is correct |
102 |
Correct |
1047 ms |
104116 KB |
Output is correct |
103 |
Correct |
1018 ms |
103948 KB |
Output is correct |
104 |
Correct |
1086 ms |
104064 KB |
Output is correct |
105 |
Correct |
1109 ms |
103876 KB |
Output is correct |
106 |
Correct |
992 ms |
107972 KB |
Output is correct |
107 |
Correct |
1016 ms |
107872 KB |
Output is correct |
108 |
Correct |
1028 ms |
110048 KB |
Output is correct |
109 |
Correct |
971 ms |
109724 KB |
Output is correct |
110 |
Correct |
1245 ms |
139856 KB |
Output is correct |
111 |
Correct |
1271 ms |
137172 KB |
Output is correct |
112 |
Correct |
1252 ms |
128996 KB |
Output is correct |
113 |
Correct |
1062 ms |
93848 KB |
Output is correct |
114 |
Correct |
1098 ms |
94456 KB |
Output is correct |