#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e6+5;
int par[maxn];
int find(int x) {return x==par[x]?x:par[x] = find(par[x]);}
int cc = 0;
vector<int> g[maxn];
void mg(int a, int b) {
int A=find(a), B=find(b);
if (A!=B) {
--cc;
par[A] = B;
g[a].pb(b); g[b].pb(a);
bug(a,b);
}
}
int col[maxn];
void dfs(int v) {
for (int u : g[v]) {
if (col[u] == -1) {
col[u] = col[v] ^ 1;
dfs(u);
}
}
}
struct seg{
int l,r,i;
};
int who[maxn];
bool pluck[maxn];
int myl[maxn], myi[maxn];
signed main(){
IOS();
memset(col, -1, sizeof col);
int n; cin>>n;
REP(i,n) par[i] = i;
vector<seg> v;
cc = n;
REP(i,n) {
int a,b; cin>>a>>b;
v.pb({a,b,i});
who[a]=who[b]=i; pluck[b] = 1;
}
REP(hi,2) {
vector<seg>q;
memset(myi, -1, sizeof myi);
for (seg &s : v) {
myl[s.r] = s.l; myi[s.r] = s.i;
}
// sort(ALL(v), [&](seg a, seg b){return a.r < b.r;});
REP1(i,2*n) {
if (myi[i] == -1) continue;
int eye = myi[i], el = myl[i];
while (!q.empty() && q.back().l > el) q.pop_back();
if (!q.empty() && q.back().r > el) {
mg(eye, q.back().i);
// if (q.back().i==0 && v[i].i==2) {
// bug(q.back().r, v[i].l);
// }
// q.back().r = v[i].r; q.back().
// }else{
}
q.pb({el,i,eye});
}
// bug("HO");
for (seg & s : v) {
s.l=2*n+1-s.l; s.r=2*n+1-s.r;
swap(s.l, s.r);
}
}
bug(cc);
REP(i,n) {
if (col[i] == -1) {
col[i] = 0; dfs(i);
}
}
REP(i,n) bug(i, col[i]);
vector<int> s1,s2; s1.pb(-1); s2.pb(-1);
REP1(i,2*n){
if (pluck[i]) {
if (s1.back()==who[i]) s1.pop_back();
else if (s2.back()==who[i]) s2.pop_back();
else GG();
}else{
(col[who[i]]?s1:s2).pb(who[i]);
}
}
cout<<mpow(2,cc)<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
62956 KB |
Output is correct |
2 |
Correct |
42 ms |
62976 KB |
Output is correct |
3 |
Correct |
42 ms |
62956 KB |
Output is correct |
4 |
Correct |
42 ms |
62976 KB |
Output is correct |
5 |
Correct |
42 ms |
62956 KB |
Output is correct |
6 |
Correct |
41 ms |
62956 KB |
Output is correct |
7 |
Correct |
42 ms |
62956 KB |
Output is correct |
8 |
Correct |
42 ms |
62956 KB |
Output is correct |
9 |
Correct |
42 ms |
62956 KB |
Output is correct |
10 |
Correct |
41 ms |
62956 KB |
Output is correct |
11 |
Correct |
42 ms |
62956 KB |
Output is correct |
12 |
Correct |
42 ms |
62956 KB |
Output is correct |
13 |
Correct |
42 ms |
62956 KB |
Output is correct |
14 |
Correct |
42 ms |
62956 KB |
Output is correct |
15 |
Correct |
42 ms |
62956 KB |
Output is correct |
16 |
Correct |
42 ms |
62956 KB |
Output is correct |
17 |
Correct |
42 ms |
62956 KB |
Output is correct |
18 |
Correct |
42 ms |
62956 KB |
Output is correct |
19 |
Correct |
43 ms |
63084 KB |
Output is correct |
20 |
Correct |
41 ms |
62956 KB |
Output is correct |
21 |
Correct |
42 ms |
62956 KB |
Output is correct |
22 |
Correct |
42 ms |
63084 KB |
Output is correct |
23 |
Correct |
42 ms |
62956 KB |
Output is correct |
24 |
Correct |
42 ms |
62956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
62956 KB |
Output is correct |
2 |
Correct |
42 ms |
62976 KB |
Output is correct |
3 |
Correct |
42 ms |
62956 KB |
Output is correct |
4 |
Correct |
42 ms |
62976 KB |
Output is correct |
5 |
Correct |
42 ms |
62956 KB |
Output is correct |
6 |
Correct |
41 ms |
62956 KB |
Output is correct |
7 |
Correct |
42 ms |
62956 KB |
Output is correct |
8 |
Correct |
42 ms |
62956 KB |
Output is correct |
9 |
Correct |
42 ms |
62956 KB |
Output is correct |
10 |
Correct |
41 ms |
62956 KB |
Output is correct |
11 |
Correct |
42 ms |
62956 KB |
Output is correct |
12 |
Correct |
42 ms |
62956 KB |
Output is correct |
13 |
Correct |
42 ms |
62956 KB |
Output is correct |
14 |
Correct |
42 ms |
62956 KB |
Output is correct |
15 |
Correct |
42 ms |
62956 KB |
Output is correct |
16 |
Correct |
42 ms |
62956 KB |
Output is correct |
17 |
Correct |
42 ms |
62956 KB |
Output is correct |
18 |
Correct |
42 ms |
62956 KB |
Output is correct |
19 |
Correct |
43 ms |
63084 KB |
Output is correct |
20 |
Correct |
41 ms |
62956 KB |
Output is correct |
21 |
Correct |
42 ms |
62956 KB |
Output is correct |
22 |
Correct |
42 ms |
63084 KB |
Output is correct |
23 |
Correct |
42 ms |
62956 KB |
Output is correct |
24 |
Correct |
42 ms |
62956 KB |
Output is correct |
25 |
Correct |
43 ms |
63084 KB |
Output is correct |
26 |
Correct |
43 ms |
63084 KB |
Output is correct |
27 |
Correct |
44 ms |
63340 KB |
Output is correct |
28 |
Correct |
43 ms |
63104 KB |
Output is correct |
29 |
Correct |
43 ms |
63084 KB |
Output is correct |
30 |
Correct |
43 ms |
63084 KB |
Output is correct |
31 |
Correct |
44 ms |
63212 KB |
Output is correct |
32 |
Correct |
42 ms |
63084 KB |
Output is correct |
33 |
Correct |
42 ms |
63212 KB |
Output is correct |
34 |
Correct |
44 ms |
63084 KB |
Output is correct |
35 |
Correct |
42 ms |
63084 KB |
Output is correct |
36 |
Correct |
42 ms |
63084 KB |
Output is correct |
37 |
Correct |
42 ms |
63212 KB |
Output is correct |
38 |
Correct |
43 ms |
63232 KB |
Output is correct |
39 |
Correct |
42 ms |
63212 KB |
Output is correct |
40 |
Correct |
43 ms |
63084 KB |
Output is correct |
41 |
Correct |
43 ms |
63084 KB |
Output is correct |
42 |
Correct |
44 ms |
63084 KB |
Output is correct |
43 |
Correct |
43 ms |
63468 KB |
Output is correct |
44 |
Correct |
43 ms |
63212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
62956 KB |
Output is correct |
2 |
Correct |
42 ms |
62976 KB |
Output is correct |
3 |
Correct |
42 ms |
62956 KB |
Output is correct |
4 |
Correct |
42 ms |
62976 KB |
Output is correct |
5 |
Correct |
42 ms |
62956 KB |
Output is correct |
6 |
Correct |
41 ms |
62956 KB |
Output is correct |
7 |
Correct |
42 ms |
62956 KB |
Output is correct |
8 |
Correct |
42 ms |
62956 KB |
Output is correct |
9 |
Correct |
42 ms |
62956 KB |
Output is correct |
10 |
Correct |
41 ms |
62956 KB |
Output is correct |
11 |
Correct |
42 ms |
62956 KB |
Output is correct |
12 |
Correct |
42 ms |
62956 KB |
Output is correct |
13 |
Correct |
42 ms |
62956 KB |
Output is correct |
14 |
Correct |
42 ms |
62956 KB |
Output is correct |
15 |
Correct |
42 ms |
62956 KB |
Output is correct |
16 |
Correct |
42 ms |
62956 KB |
Output is correct |
17 |
Correct |
42 ms |
62956 KB |
Output is correct |
18 |
Correct |
42 ms |
62956 KB |
Output is correct |
19 |
Correct |
43 ms |
63084 KB |
Output is correct |
20 |
Correct |
41 ms |
62956 KB |
Output is correct |
21 |
Correct |
42 ms |
62956 KB |
Output is correct |
22 |
Correct |
42 ms |
63084 KB |
Output is correct |
23 |
Correct |
42 ms |
62956 KB |
Output is correct |
24 |
Correct |
42 ms |
62956 KB |
Output is correct |
25 |
Correct |
43 ms |
63084 KB |
Output is correct |
26 |
Correct |
43 ms |
63084 KB |
Output is correct |
27 |
Correct |
44 ms |
63340 KB |
Output is correct |
28 |
Correct |
43 ms |
63104 KB |
Output is correct |
29 |
Correct |
43 ms |
63084 KB |
Output is correct |
30 |
Correct |
43 ms |
63084 KB |
Output is correct |
31 |
Correct |
44 ms |
63212 KB |
Output is correct |
32 |
Correct |
42 ms |
63084 KB |
Output is correct |
33 |
Correct |
42 ms |
63212 KB |
Output is correct |
34 |
Correct |
44 ms |
63084 KB |
Output is correct |
35 |
Correct |
42 ms |
63084 KB |
Output is correct |
36 |
Correct |
42 ms |
63084 KB |
Output is correct |
37 |
Correct |
42 ms |
63212 KB |
Output is correct |
38 |
Correct |
43 ms |
63232 KB |
Output is correct |
39 |
Correct |
42 ms |
63212 KB |
Output is correct |
40 |
Correct |
43 ms |
63084 KB |
Output is correct |
41 |
Correct |
43 ms |
63084 KB |
Output is correct |
42 |
Correct |
44 ms |
63084 KB |
Output is correct |
43 |
Correct |
43 ms |
63468 KB |
Output is correct |
44 |
Correct |
43 ms |
63212 KB |
Output is correct |
45 |
Correct |
94 ms |
69852 KB |
Output is correct |
46 |
Correct |
94 ms |
69980 KB |
Output is correct |
47 |
Correct |
95 ms |
69852 KB |
Output is correct |
48 |
Correct |
97 ms |
69980 KB |
Output is correct |
49 |
Correct |
99 ms |
69980 KB |
Output is correct |
50 |
Correct |
94 ms |
69724 KB |
Output is correct |
51 |
Correct |
95 ms |
69980 KB |
Output is correct |
52 |
Correct |
76 ms |
69724 KB |
Output is correct |
53 |
Correct |
72 ms |
67420 KB |
Output is correct |
54 |
Correct |
97 ms |
73268 KB |
Output is correct |
55 |
Correct |
94 ms |
72392 KB |
Output is correct |
56 |
Correct |
96 ms |
72264 KB |
Output is correct |
57 |
Correct |
94 ms |
72776 KB |
Output is correct |
58 |
Correct |
71 ms |
68364 KB |
Output is correct |
59 |
Correct |
78 ms |
68188 KB |
Output is correct |
60 |
Correct |
91 ms |
69084 KB |
Output is correct |
61 |
Correct |
96 ms |
69724 KB |
Output is correct |
62 |
Correct |
80 ms |
68956 KB |
Output is correct |
63 |
Correct |
89 ms |
69212 KB |
Output is correct |
64 |
Correct |
90 ms |
69596 KB |
Output is correct |
65 |
Correct |
95 ms |
70364 KB |
Output is correct |
66 |
Correct |
92 ms |
70364 KB |
Output is correct |
67 |
Correct |
87 ms |
70876 KB |
Output is correct |
68 |
Correct |
91 ms |
70880 KB |
Output is correct |
69 |
Correct |
88 ms |
71260 KB |
Output is correct |
70 |
Correct |
91 ms |
71260 KB |
Output is correct |
71 |
Correct |
85 ms |
70620 KB |
Output is correct |
72 |
Correct |
90 ms |
70620 KB |
Output is correct |
73 |
Correct |
88 ms |
71004 KB |
Output is correct |
74 |
Correct |
87 ms |
71004 KB |
Output is correct |
75 |
Correct |
99 ms |
73012 KB |
Output is correct |
76 |
Correct |
95 ms |
72904 KB |
Output is correct |
77 |
Correct |
95 ms |
74036 KB |
Output is correct |
78 |
Correct |
93 ms |
69980 KB |
Output is correct |
79 |
Correct |
96 ms |
69980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
62956 KB |
Output is correct |
2 |
Correct |
42 ms |
62976 KB |
Output is correct |
3 |
Correct |
42 ms |
62956 KB |
Output is correct |
4 |
Correct |
42 ms |
62976 KB |
Output is correct |
5 |
Correct |
42 ms |
62956 KB |
Output is correct |
6 |
Correct |
41 ms |
62956 KB |
Output is correct |
7 |
Correct |
42 ms |
62956 KB |
Output is correct |
8 |
Correct |
42 ms |
62956 KB |
Output is correct |
9 |
Correct |
42 ms |
62956 KB |
Output is correct |
10 |
Correct |
41 ms |
62956 KB |
Output is correct |
11 |
Correct |
42 ms |
62956 KB |
Output is correct |
12 |
Correct |
42 ms |
62956 KB |
Output is correct |
13 |
Correct |
42 ms |
62956 KB |
Output is correct |
14 |
Correct |
42 ms |
62956 KB |
Output is correct |
15 |
Correct |
42 ms |
62956 KB |
Output is correct |
16 |
Correct |
42 ms |
62956 KB |
Output is correct |
17 |
Correct |
42 ms |
62956 KB |
Output is correct |
18 |
Correct |
42 ms |
62956 KB |
Output is correct |
19 |
Correct |
43 ms |
63084 KB |
Output is correct |
20 |
Correct |
41 ms |
62956 KB |
Output is correct |
21 |
Correct |
42 ms |
62956 KB |
Output is correct |
22 |
Correct |
42 ms |
63084 KB |
Output is correct |
23 |
Correct |
42 ms |
62956 KB |
Output is correct |
24 |
Correct |
42 ms |
62956 KB |
Output is correct |
25 |
Correct |
43 ms |
63084 KB |
Output is correct |
26 |
Correct |
43 ms |
63084 KB |
Output is correct |
27 |
Correct |
44 ms |
63340 KB |
Output is correct |
28 |
Correct |
43 ms |
63104 KB |
Output is correct |
29 |
Correct |
43 ms |
63084 KB |
Output is correct |
30 |
Correct |
43 ms |
63084 KB |
Output is correct |
31 |
Correct |
44 ms |
63212 KB |
Output is correct |
32 |
Correct |
42 ms |
63084 KB |
Output is correct |
33 |
Correct |
42 ms |
63212 KB |
Output is correct |
34 |
Correct |
44 ms |
63084 KB |
Output is correct |
35 |
Correct |
42 ms |
63084 KB |
Output is correct |
36 |
Correct |
42 ms |
63084 KB |
Output is correct |
37 |
Correct |
42 ms |
63212 KB |
Output is correct |
38 |
Correct |
43 ms |
63232 KB |
Output is correct |
39 |
Correct |
42 ms |
63212 KB |
Output is correct |
40 |
Correct |
43 ms |
63084 KB |
Output is correct |
41 |
Correct |
43 ms |
63084 KB |
Output is correct |
42 |
Correct |
44 ms |
63084 KB |
Output is correct |
43 |
Correct |
43 ms |
63468 KB |
Output is correct |
44 |
Correct |
43 ms |
63212 KB |
Output is correct |
45 |
Correct |
94 ms |
69852 KB |
Output is correct |
46 |
Correct |
94 ms |
69980 KB |
Output is correct |
47 |
Correct |
95 ms |
69852 KB |
Output is correct |
48 |
Correct |
97 ms |
69980 KB |
Output is correct |
49 |
Correct |
99 ms |
69980 KB |
Output is correct |
50 |
Correct |
94 ms |
69724 KB |
Output is correct |
51 |
Correct |
95 ms |
69980 KB |
Output is correct |
52 |
Correct |
76 ms |
69724 KB |
Output is correct |
53 |
Correct |
72 ms |
67420 KB |
Output is correct |
54 |
Correct |
97 ms |
73268 KB |
Output is correct |
55 |
Correct |
94 ms |
72392 KB |
Output is correct |
56 |
Correct |
96 ms |
72264 KB |
Output is correct |
57 |
Correct |
94 ms |
72776 KB |
Output is correct |
58 |
Correct |
71 ms |
68364 KB |
Output is correct |
59 |
Correct |
78 ms |
68188 KB |
Output is correct |
60 |
Correct |
91 ms |
69084 KB |
Output is correct |
61 |
Correct |
96 ms |
69724 KB |
Output is correct |
62 |
Correct |
80 ms |
68956 KB |
Output is correct |
63 |
Correct |
89 ms |
69212 KB |
Output is correct |
64 |
Correct |
90 ms |
69596 KB |
Output is correct |
65 |
Correct |
95 ms |
70364 KB |
Output is correct |
66 |
Correct |
92 ms |
70364 KB |
Output is correct |
67 |
Correct |
87 ms |
70876 KB |
Output is correct |
68 |
Correct |
91 ms |
70880 KB |
Output is correct |
69 |
Correct |
88 ms |
71260 KB |
Output is correct |
70 |
Correct |
91 ms |
71260 KB |
Output is correct |
71 |
Correct |
85 ms |
70620 KB |
Output is correct |
72 |
Correct |
90 ms |
70620 KB |
Output is correct |
73 |
Correct |
88 ms |
71004 KB |
Output is correct |
74 |
Correct |
87 ms |
71004 KB |
Output is correct |
75 |
Correct |
99 ms |
73012 KB |
Output is correct |
76 |
Correct |
95 ms |
72904 KB |
Output is correct |
77 |
Correct |
95 ms |
74036 KB |
Output is correct |
78 |
Correct |
93 ms |
69980 KB |
Output is correct |
79 |
Correct |
96 ms |
69980 KB |
Output is correct |
80 |
Correct |
946 ms |
126268 KB |
Output is correct |
81 |
Correct |
912 ms |
126652 KB |
Output is correct |
82 |
Correct |
921 ms |
127376 KB |
Output is correct |
83 |
Correct |
920 ms |
127420 KB |
Output is correct |
84 |
Correct |
940 ms |
127548 KB |
Output is correct |
85 |
Correct |
981 ms |
126652 KB |
Output is correct |
86 |
Correct |
973 ms |
127164 KB |
Output is correct |
87 |
Correct |
477 ms |
121672 KB |
Output is correct |
88 |
Correct |
446 ms |
100668 KB |
Output is correct |
89 |
Correct |
948 ms |
154468 KB |
Output is correct |
90 |
Correct |
955 ms |
148708 KB |
Output is correct |
91 |
Correct |
945 ms |
147932 KB |
Output is correct |
92 |
Correct |
869 ms |
153116 KB |
Output is correct |
93 |
Correct |
473 ms |
109516 KB |
Output is correct |
94 |
Correct |
668 ms |
114108 KB |
Output is correct |
95 |
Correct |
894 ms |
123708 KB |
Output is correct |
96 |
Correct |
930 ms |
126776 KB |
Output is correct |
97 |
Correct |
720 ms |
117308 KB |
Output is correct |
98 |
Correct |
910 ms |
122940 KB |
Output is correct |
99 |
Correct |
940 ms |
124684 KB |
Output is correct |
100 |
Correct |
971 ms |
130112 KB |
Output is correct |
101 |
Correct |
956 ms |
130236 KB |
Output is correct |
102 |
Correct |
929 ms |
135868 KB |
Output is correct |
103 |
Correct |
859 ms |
135800 KB |
Output is correct |
104 |
Correct |
893 ms |
138592 KB |
Output is correct |
105 |
Correct |
896 ms |
138684 KB |
Output is correct |
106 |
Correct |
908 ms |
133180 KB |
Output is correct |
107 |
Correct |
887 ms |
133256 KB |
Output is correct |
108 |
Correct |
868 ms |
135296 KB |
Output is correct |
109 |
Correct |
839 ms |
135340 KB |
Output is correct |
110 |
Correct |
1000 ms |
174164 KB |
Output is correct |
111 |
Correct |
990 ms |
171300 KB |
Output is correct |
112 |
Correct |
1002 ms |
163356 KB |
Output is correct |
113 |
Correct |
951 ms |
126484 KB |
Output is correct |
114 |
Correct |
941 ms |
126268 KB |
Output is correct |