#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7;
const int LIM=1e6+7;
vector<pair<int,int>>V[LIM];
ll ans=1;
pair<int,int>T[LIM];
int kol[LIM], tr[8*LIM], kto[8*LIM], trmi[8*LIM], N=1;
void DFS(int x, int o) {
for(auto i : V[x]) {
if(!kol[i.st]) {
kol[i.st]=kol[x]^i.nd;
DFS(i.st, x);
} else if((kol[i.st]^i.nd)!=kol[x]) ans=0;
}
}
void dodaj(int a, int b) {
if(b==-1) return;
if(T[b].st<T[a].st) {
V[a].pb({b, 3});
V[b].pb({a, 3});
}
}
void upd(int l, int r, int x, int a) {
if(l>r) return;
l+=N; r+=N;
tr[l]=max(tr[l], x);
dodaj(a, trmi[l]);
tr[r]=max(tr[r], x);
dodaj(a, trmi[r]);
while(l/2!=r/2) {
if(l%2==0) {
tr[l+1]=max(tr[l+1], x);
dodaj(a, trmi[l+1]);
}
if(r%2==1) {
tr[r-1]=max(tr[r-1], x);
dodaj(a, trmi[r-1]);
}
l/=2; r/=2;
}
}
vector<pair<int,int>>zejdz(int v, int a, int b) {
trmi[v]=-1;
if(a==b) {
if(kto[a]==-1) return {};
trmi[v]=kto[a];
return {{T[kto[a]].st, kto[a]}};
}
int mid=(a+b)/2;
vector<pair<int,int>>A=zejdz(2*v, a, mid), B=zejdz(2*v+1, mid+1, b);
vector<pair<int,int>>C;
int l=0;
for(auto i : A) {
while(l<B.size() && B[l]<=i) C.pb(B[l++]);
C.pb(i);
}
while(l<B.size()) C.pb(B[l++]);
l=0;
while(l+1<C.size() && C[l+1].st<=tr[v]) {
V[C[l].nd].pb({C[l+1].nd, 0});
V[C[l+1].nd].pb({C[l].nd, 0});
++l;
}
if(C.size()) trmi[v]=C[0].nd; else trmi[v]=-1;
return C;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
while(N<2*n) N*=2;
rep(i, 2*N) tr[i]=-MOD;
rep(i, N) kto[i]=-1;
rep(i, n) {
cin >> T[i].st >> T[i].nd;
--T[i].st; --T[i].nd;
}
sort(T, T+n);
rep(i, n) kto[T[i].nd]=i;
zejdz(1, 0, N-1);
rep(i, n) upd(T[i].st+1, T[i].nd-1, T[i].st-1, i);
zejdz(1, 0, N-1);
rep(i, n) if(!kol[i]) {
kol[i]=1;
DFS(i, i);
ans=(ans*2)%MOD;
}
cout << ans << '\n';
}
Compilation message
port_facility.cpp: In function 'std::vector<std::pair<int, int> > zejdz(int, int, int)':
port_facility.cpp:62:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | while(l<B.size() && B[l]<=i) C.pb(B[l++]);
| ~^~~~~~~~~
port_facility.cpp:65:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | while(l<B.size()) C.pb(B[l++]);
| ~^~~~~~~~~
port_facility.cpp:67:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | while(l+1<C.size() && C[l+1].st<=tr[v]) {
| ~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
30812 KB |
Output is correct |
2 |
Correct |
6 ms |
30812 KB |
Output is correct |
3 |
Correct |
5 ms |
30808 KB |
Output is correct |
4 |
Correct |
4 ms |
30812 KB |
Output is correct |
5 |
Correct |
5 ms |
30812 KB |
Output is correct |
6 |
Correct |
5 ms |
30812 KB |
Output is correct |
7 |
Correct |
5 ms |
30812 KB |
Output is correct |
8 |
Correct |
5 ms |
30812 KB |
Output is correct |
9 |
Correct |
5 ms |
30808 KB |
Output is correct |
10 |
Correct |
4 ms |
30812 KB |
Output is correct |
11 |
Correct |
5 ms |
30812 KB |
Output is correct |
12 |
Correct |
5 ms |
30808 KB |
Output is correct |
13 |
Correct |
5 ms |
30944 KB |
Output is correct |
14 |
Correct |
5 ms |
30812 KB |
Output is correct |
15 |
Correct |
5 ms |
30812 KB |
Output is correct |
16 |
Correct |
5 ms |
30812 KB |
Output is correct |
17 |
Correct |
5 ms |
30812 KB |
Output is correct |
18 |
Correct |
6 ms |
30812 KB |
Output is correct |
19 |
Correct |
5 ms |
30932 KB |
Output is correct |
20 |
Correct |
5 ms |
30808 KB |
Output is correct |
21 |
Correct |
4 ms |
30812 KB |
Output is correct |
22 |
Correct |
5 ms |
30812 KB |
Output is correct |
23 |
Correct |
5 ms |
30812 KB |
Output is correct |
24 |
Correct |
5 ms |
30808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
30812 KB |
Output is correct |
2 |
Correct |
6 ms |
30812 KB |
Output is correct |
3 |
Correct |
5 ms |
30808 KB |
Output is correct |
4 |
Correct |
4 ms |
30812 KB |
Output is correct |
5 |
Correct |
5 ms |
30812 KB |
Output is correct |
6 |
Correct |
5 ms |
30812 KB |
Output is correct |
7 |
Correct |
5 ms |
30812 KB |
Output is correct |
8 |
Correct |
5 ms |
30812 KB |
Output is correct |
9 |
Correct |
5 ms |
30808 KB |
Output is correct |
10 |
Correct |
4 ms |
30812 KB |
Output is correct |
11 |
Correct |
5 ms |
30812 KB |
Output is correct |
12 |
Correct |
5 ms |
30808 KB |
Output is correct |
13 |
Correct |
5 ms |
30944 KB |
Output is correct |
14 |
Correct |
5 ms |
30812 KB |
Output is correct |
15 |
Correct |
5 ms |
30812 KB |
Output is correct |
16 |
Correct |
5 ms |
30812 KB |
Output is correct |
17 |
Correct |
5 ms |
30812 KB |
Output is correct |
18 |
Correct |
6 ms |
30812 KB |
Output is correct |
19 |
Correct |
5 ms |
30932 KB |
Output is correct |
20 |
Correct |
5 ms |
30808 KB |
Output is correct |
21 |
Correct |
4 ms |
30812 KB |
Output is correct |
22 |
Correct |
5 ms |
30812 KB |
Output is correct |
23 |
Correct |
5 ms |
30812 KB |
Output is correct |
24 |
Correct |
5 ms |
30808 KB |
Output is correct |
25 |
Correct |
6 ms |
31068 KB |
Output is correct |
26 |
Correct |
6 ms |
31216 KB |
Output is correct |
27 |
Correct |
7 ms |
31092 KB |
Output is correct |
28 |
Correct |
6 ms |
31200 KB |
Output is correct |
29 |
Correct |
7 ms |
31064 KB |
Output is correct |
30 |
Correct |
6 ms |
31208 KB |
Output is correct |
31 |
Correct |
6 ms |
30968 KB |
Output is correct |
32 |
Correct |
6 ms |
31068 KB |
Output is correct |
33 |
Correct |
6 ms |
31068 KB |
Output is correct |
34 |
Correct |
7 ms |
31068 KB |
Output is correct |
35 |
Correct |
6 ms |
30812 KB |
Output is correct |
36 |
Correct |
6 ms |
31068 KB |
Output is correct |
37 |
Correct |
7 ms |
31580 KB |
Output is correct |
38 |
Correct |
6 ms |
31580 KB |
Output is correct |
39 |
Correct |
6 ms |
31068 KB |
Output is correct |
40 |
Correct |
6 ms |
31056 KB |
Output is correct |
41 |
Correct |
6 ms |
31068 KB |
Output is correct |
42 |
Correct |
6 ms |
31068 KB |
Output is correct |
43 |
Correct |
6 ms |
31068 KB |
Output is correct |
44 |
Correct |
6 ms |
31224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
30812 KB |
Output is correct |
2 |
Correct |
6 ms |
30812 KB |
Output is correct |
3 |
Correct |
5 ms |
30808 KB |
Output is correct |
4 |
Correct |
4 ms |
30812 KB |
Output is correct |
5 |
Correct |
5 ms |
30812 KB |
Output is correct |
6 |
Correct |
5 ms |
30812 KB |
Output is correct |
7 |
Correct |
5 ms |
30812 KB |
Output is correct |
8 |
Correct |
5 ms |
30812 KB |
Output is correct |
9 |
Correct |
5 ms |
30808 KB |
Output is correct |
10 |
Correct |
4 ms |
30812 KB |
Output is correct |
11 |
Correct |
5 ms |
30812 KB |
Output is correct |
12 |
Correct |
5 ms |
30808 KB |
Output is correct |
13 |
Correct |
5 ms |
30944 KB |
Output is correct |
14 |
Correct |
5 ms |
30812 KB |
Output is correct |
15 |
Correct |
5 ms |
30812 KB |
Output is correct |
16 |
Correct |
5 ms |
30812 KB |
Output is correct |
17 |
Correct |
5 ms |
30812 KB |
Output is correct |
18 |
Correct |
6 ms |
30812 KB |
Output is correct |
19 |
Correct |
5 ms |
30932 KB |
Output is correct |
20 |
Correct |
5 ms |
30808 KB |
Output is correct |
21 |
Correct |
4 ms |
30812 KB |
Output is correct |
22 |
Correct |
5 ms |
30812 KB |
Output is correct |
23 |
Correct |
5 ms |
30812 KB |
Output is correct |
24 |
Correct |
5 ms |
30808 KB |
Output is correct |
25 |
Correct |
6 ms |
31068 KB |
Output is correct |
26 |
Correct |
6 ms |
31216 KB |
Output is correct |
27 |
Correct |
7 ms |
31092 KB |
Output is correct |
28 |
Correct |
6 ms |
31200 KB |
Output is correct |
29 |
Correct |
7 ms |
31064 KB |
Output is correct |
30 |
Correct |
6 ms |
31208 KB |
Output is correct |
31 |
Correct |
6 ms |
30968 KB |
Output is correct |
32 |
Correct |
6 ms |
31068 KB |
Output is correct |
33 |
Correct |
6 ms |
31068 KB |
Output is correct |
34 |
Correct |
7 ms |
31068 KB |
Output is correct |
35 |
Correct |
6 ms |
30812 KB |
Output is correct |
36 |
Correct |
6 ms |
31068 KB |
Output is correct |
37 |
Correct |
7 ms |
31580 KB |
Output is correct |
38 |
Correct |
6 ms |
31580 KB |
Output is correct |
39 |
Correct |
6 ms |
31068 KB |
Output is correct |
40 |
Correct |
6 ms |
31056 KB |
Output is correct |
41 |
Correct |
6 ms |
31068 KB |
Output is correct |
42 |
Correct |
6 ms |
31068 KB |
Output is correct |
43 |
Correct |
6 ms |
31068 KB |
Output is correct |
44 |
Correct |
6 ms |
31224 KB |
Output is correct |
45 |
Correct |
81 ms |
45948 KB |
Output is correct |
46 |
Correct |
83 ms |
46976 KB |
Output is correct |
47 |
Correct |
80 ms |
45428 KB |
Output is correct |
48 |
Correct |
83 ms |
46804 KB |
Output is correct |
49 |
Correct |
75 ms |
45820 KB |
Output is correct |
50 |
Correct |
89 ms |
46840 KB |
Output is correct |
51 |
Correct |
83 ms |
46948 KB |
Output is correct |
52 |
Correct |
49 ms |
39072 KB |
Output is correct |
53 |
Correct |
55 ms |
39300 KB |
Output is correct |
54 |
Correct |
130 ms |
82092 KB |
Output is correct |
55 |
Correct |
130 ms |
77728 KB |
Output is correct |
56 |
Correct |
124 ms |
77720 KB |
Output is correct |
57 |
Correct |
56 ms |
42148 KB |
Output is correct |
58 |
Correct |
52 ms |
39072 KB |
Output is correct |
59 |
Correct |
59 ms |
40032 KB |
Output is correct |
60 |
Correct |
66 ms |
41512 KB |
Output is correct |
61 |
Correct |
72 ms |
43052 KB |
Output is correct |
62 |
Correct |
66 ms |
43064 KB |
Output is correct |
63 |
Correct |
72 ms |
42300 KB |
Output is correct |
64 |
Correct |
76 ms |
43364 KB |
Output is correct |
65 |
Correct |
225 ms |
103212 KB |
Output is correct |
66 |
Correct |
221 ms |
103480 KB |
Output is correct |
67 |
Correct |
104 ms |
60068 KB |
Output is correct |
68 |
Correct |
123 ms |
60088 KB |
Output is correct |
69 |
Correct |
98 ms |
59812 KB |
Output is correct |
70 |
Correct |
101 ms |
59868 KB |
Output is correct |
71 |
Correct |
68 ms |
46704 KB |
Output is correct |
72 |
Correct |
73 ms |
46680 KB |
Output is correct |
73 |
Correct |
66 ms |
45660 KB |
Output is correct |
74 |
Correct |
65 ms |
45688 KB |
Output is correct |
75 |
Correct |
58 ms |
44796 KB |
Output is correct |
76 |
Correct |
61 ms |
45588 KB |
Output is correct |
77 |
Correct |
60 ms |
44632 KB |
Output is correct |
78 |
Correct |
85 ms |
46724 KB |
Output is correct |
79 |
Correct |
89 ms |
46176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
30812 KB |
Output is correct |
2 |
Correct |
6 ms |
30812 KB |
Output is correct |
3 |
Correct |
5 ms |
30808 KB |
Output is correct |
4 |
Correct |
4 ms |
30812 KB |
Output is correct |
5 |
Correct |
5 ms |
30812 KB |
Output is correct |
6 |
Correct |
5 ms |
30812 KB |
Output is correct |
7 |
Correct |
5 ms |
30812 KB |
Output is correct |
8 |
Correct |
5 ms |
30812 KB |
Output is correct |
9 |
Correct |
5 ms |
30808 KB |
Output is correct |
10 |
Correct |
4 ms |
30812 KB |
Output is correct |
11 |
Correct |
5 ms |
30812 KB |
Output is correct |
12 |
Correct |
5 ms |
30808 KB |
Output is correct |
13 |
Correct |
5 ms |
30944 KB |
Output is correct |
14 |
Correct |
5 ms |
30812 KB |
Output is correct |
15 |
Correct |
5 ms |
30812 KB |
Output is correct |
16 |
Correct |
5 ms |
30812 KB |
Output is correct |
17 |
Correct |
5 ms |
30812 KB |
Output is correct |
18 |
Correct |
6 ms |
30812 KB |
Output is correct |
19 |
Correct |
5 ms |
30932 KB |
Output is correct |
20 |
Correct |
5 ms |
30808 KB |
Output is correct |
21 |
Correct |
4 ms |
30812 KB |
Output is correct |
22 |
Correct |
5 ms |
30812 KB |
Output is correct |
23 |
Correct |
5 ms |
30812 KB |
Output is correct |
24 |
Correct |
5 ms |
30808 KB |
Output is correct |
25 |
Correct |
6 ms |
31068 KB |
Output is correct |
26 |
Correct |
6 ms |
31216 KB |
Output is correct |
27 |
Correct |
7 ms |
31092 KB |
Output is correct |
28 |
Correct |
6 ms |
31200 KB |
Output is correct |
29 |
Correct |
7 ms |
31064 KB |
Output is correct |
30 |
Correct |
6 ms |
31208 KB |
Output is correct |
31 |
Correct |
6 ms |
30968 KB |
Output is correct |
32 |
Correct |
6 ms |
31068 KB |
Output is correct |
33 |
Correct |
6 ms |
31068 KB |
Output is correct |
34 |
Correct |
7 ms |
31068 KB |
Output is correct |
35 |
Correct |
6 ms |
30812 KB |
Output is correct |
36 |
Correct |
6 ms |
31068 KB |
Output is correct |
37 |
Correct |
7 ms |
31580 KB |
Output is correct |
38 |
Correct |
6 ms |
31580 KB |
Output is correct |
39 |
Correct |
6 ms |
31068 KB |
Output is correct |
40 |
Correct |
6 ms |
31056 KB |
Output is correct |
41 |
Correct |
6 ms |
31068 KB |
Output is correct |
42 |
Correct |
6 ms |
31068 KB |
Output is correct |
43 |
Correct |
6 ms |
31068 KB |
Output is correct |
44 |
Correct |
6 ms |
31224 KB |
Output is correct |
45 |
Correct |
81 ms |
45948 KB |
Output is correct |
46 |
Correct |
83 ms |
46976 KB |
Output is correct |
47 |
Correct |
80 ms |
45428 KB |
Output is correct |
48 |
Correct |
83 ms |
46804 KB |
Output is correct |
49 |
Correct |
75 ms |
45820 KB |
Output is correct |
50 |
Correct |
89 ms |
46840 KB |
Output is correct |
51 |
Correct |
83 ms |
46948 KB |
Output is correct |
52 |
Correct |
49 ms |
39072 KB |
Output is correct |
53 |
Correct |
55 ms |
39300 KB |
Output is correct |
54 |
Correct |
130 ms |
82092 KB |
Output is correct |
55 |
Correct |
130 ms |
77728 KB |
Output is correct |
56 |
Correct |
124 ms |
77720 KB |
Output is correct |
57 |
Correct |
56 ms |
42148 KB |
Output is correct |
58 |
Correct |
52 ms |
39072 KB |
Output is correct |
59 |
Correct |
59 ms |
40032 KB |
Output is correct |
60 |
Correct |
66 ms |
41512 KB |
Output is correct |
61 |
Correct |
72 ms |
43052 KB |
Output is correct |
62 |
Correct |
66 ms |
43064 KB |
Output is correct |
63 |
Correct |
72 ms |
42300 KB |
Output is correct |
64 |
Correct |
76 ms |
43364 KB |
Output is correct |
65 |
Correct |
225 ms |
103212 KB |
Output is correct |
66 |
Correct |
221 ms |
103480 KB |
Output is correct |
67 |
Correct |
104 ms |
60068 KB |
Output is correct |
68 |
Correct |
123 ms |
60088 KB |
Output is correct |
69 |
Correct |
98 ms |
59812 KB |
Output is correct |
70 |
Correct |
101 ms |
59868 KB |
Output is correct |
71 |
Correct |
68 ms |
46704 KB |
Output is correct |
72 |
Correct |
73 ms |
46680 KB |
Output is correct |
73 |
Correct |
66 ms |
45660 KB |
Output is correct |
74 |
Correct |
65 ms |
45688 KB |
Output is correct |
75 |
Correct |
58 ms |
44796 KB |
Output is correct |
76 |
Correct |
61 ms |
45588 KB |
Output is correct |
77 |
Correct |
60 ms |
44632 KB |
Output is correct |
78 |
Correct |
85 ms |
46724 KB |
Output is correct |
79 |
Correct |
89 ms |
46176 KB |
Output is correct |
80 |
Correct |
853 ms |
202904 KB |
Output is correct |
81 |
Correct |
888 ms |
202880 KB |
Output is correct |
82 |
Correct |
906 ms |
191336 KB |
Output is correct |
83 |
Correct |
876 ms |
203000 KB |
Output is correct |
84 |
Correct |
851 ms |
203768 KB |
Output is correct |
85 |
Correct |
865 ms |
200176 KB |
Output is correct |
86 |
Correct |
905 ms |
206336 KB |
Output is correct |
87 |
Correct |
466 ms |
116636 KB |
Output is correct |
88 |
Correct |
522 ms |
117044 KB |
Output is correct |
89 |
Correct |
1527 ms |
645820 KB |
Output is correct |
90 |
Correct |
1381 ms |
574436 KB |
Output is correct |
91 |
Correct |
1380 ms |
573952 KB |
Output is correct |
92 |
Correct |
559 ms |
148264 KB |
Output is correct |
93 |
Correct |
451 ms |
116676 KB |
Output is correct |
94 |
Correct |
574 ms |
131644 KB |
Output is correct |
95 |
Correct |
726 ms |
153108 KB |
Output is correct |
96 |
Correct |
765 ms |
174516 KB |
Output is correct |
97 |
Correct |
602 ms |
146376 KB |
Output is correct |
98 |
Correct |
728 ms |
164992 KB |
Output is correct |
99 |
Correct |
833 ms |
183736 KB |
Output is correct |
100 |
Correct |
3217 ms |
819656 KB |
Output is correct |
101 |
Correct |
3191 ms |
814344 KB |
Output is correct |
102 |
Correct |
1127 ms |
366224 KB |
Output is correct |
103 |
Correct |
1094 ms |
364192 KB |
Output is correct |
104 |
Correct |
1035 ms |
352028 KB |
Output is correct |
105 |
Correct |
1039 ms |
350036 KB |
Output is correct |
106 |
Correct |
629 ms |
174088 KB |
Output is correct |
107 |
Correct |
589 ms |
173920 KB |
Output is correct |
108 |
Correct |
585 ms |
179668 KB |
Output is correct |
109 |
Correct |
596 ms |
181900 KB |
Output is correct |
110 |
Correct |
558 ms |
173812 KB |
Output is correct |
111 |
Correct |
537 ms |
174228 KB |
Output is correct |
112 |
Correct |
569 ms |
173856 KB |
Output is correct |
113 |
Correct |
843 ms |
191068 KB |
Output is correct |
114 |
Correct |
857 ms |
202768 KB |
Output is correct |