#include <iostream>
#include <vector>
using namespace std;
vector<int> temp[1000001], color(1000001, -1);
int a[1000001], b[1000001];
bool continuar=0;
void recursion(int u){
for(int v:temp[u]){
if(color[v]==!color[u]){
continue;
} else {
if(color[v]==color[u]){
continuar=1;
cout<<0;
break;
} else {
color[v]=!color[u];
recursion(v);
if(continuar){
break;
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie();
cin.tie();
int n, z=0;
cin>>n;
int tiempo[1+2*n];
for(int i=1; i<=n; i++){
cin>>a[i]>>b[i];
tiempo[a[i]]=i;
tiempo[b[i]]=-i;
}
vector<int> lista, t[2];
for(int e=1; e<=2*n; e++){
if(tiempo[e]>0){
continue;
}
while(!lista.empty() && a[-tiempo[e]]<a[lista.back()]){
lista.pop_back();
}
if(!lista.empty() && a[-tiempo[e]] < b[lista.back()]){
temp[-tiempo[e]].push_back(lista.back());
temp[lista.back()].push_back(-tiempo[e]);
}
lista.push_back(-tiempo[e]);
}
lista.clear();
for(int e=2*n; e>=1; e--){
if(tiempo[e]<0){
continue;
}
while(!lista.empty() && b[lista.back()]<b[tiempo[e]]){
lista.pop_back();
}
if(!lista.empty() && a[lista.back()]<b[tiempo[e]]){
temp[tiempo[e]].push_back(lista.back());
temp[lista.back()].push_back(tiempo[e]);
}
lista.push_back(tiempo[e]);
}
for(int i=1; i<=n; i++){
if(color[i]!=-1){
continue;
}
z++;
color[i]=0;
recursion(i);
if(continuar){
return 0;
}
}
for(int e=1; e<=2*n; e++){
if(tiempo[e]>0){
t[color[tiempo[e]]].push_back(tiempo[e]);
} else {
if(t[color[-tiempo[e]]].back()==-tiempo[e]){
t[color[-tiempo[e]]].pop_back();
} else {
cout<<0;
return 0;
}
}
}
int total=1;
for(int x=1; x<=z; x++){
total=(2*total)%1000000007;
}
cout<<total<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
27740 KB |
Output is correct |
2 |
Correct |
13 ms |
27712 KB |
Output is correct |
3 |
Correct |
13 ms |
27680 KB |
Output is correct |
4 |
Correct |
14 ms |
27728 KB |
Output is correct |
5 |
Correct |
13 ms |
27728 KB |
Output is correct |
6 |
Correct |
13 ms |
27728 KB |
Output is correct |
7 |
Correct |
13 ms |
27664 KB |
Output is correct |
8 |
Correct |
13 ms |
27728 KB |
Output is correct |
9 |
Correct |
13 ms |
27728 KB |
Output is correct |
10 |
Correct |
15 ms |
27728 KB |
Output is correct |
11 |
Correct |
14 ms |
27732 KB |
Output is correct |
12 |
Correct |
14 ms |
27700 KB |
Output is correct |
13 |
Correct |
13 ms |
27664 KB |
Output is correct |
14 |
Correct |
14 ms |
27728 KB |
Output is correct |
15 |
Correct |
15 ms |
27684 KB |
Output is correct |
16 |
Correct |
14 ms |
27728 KB |
Output is correct |
17 |
Correct |
14 ms |
27740 KB |
Output is correct |
18 |
Correct |
13 ms |
27664 KB |
Output is correct |
19 |
Correct |
14 ms |
27728 KB |
Output is correct |
20 |
Correct |
13 ms |
27728 KB |
Output is correct |
21 |
Correct |
14 ms |
27680 KB |
Output is correct |
22 |
Correct |
13 ms |
27740 KB |
Output is correct |
23 |
Correct |
14 ms |
27640 KB |
Output is correct |
24 |
Correct |
14 ms |
27664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
27740 KB |
Output is correct |
2 |
Correct |
13 ms |
27712 KB |
Output is correct |
3 |
Correct |
13 ms |
27680 KB |
Output is correct |
4 |
Correct |
14 ms |
27728 KB |
Output is correct |
5 |
Correct |
13 ms |
27728 KB |
Output is correct |
6 |
Correct |
13 ms |
27728 KB |
Output is correct |
7 |
Correct |
13 ms |
27664 KB |
Output is correct |
8 |
Correct |
13 ms |
27728 KB |
Output is correct |
9 |
Correct |
13 ms |
27728 KB |
Output is correct |
10 |
Correct |
15 ms |
27728 KB |
Output is correct |
11 |
Correct |
14 ms |
27732 KB |
Output is correct |
12 |
Correct |
14 ms |
27700 KB |
Output is correct |
13 |
Correct |
13 ms |
27664 KB |
Output is correct |
14 |
Correct |
14 ms |
27728 KB |
Output is correct |
15 |
Correct |
15 ms |
27684 KB |
Output is correct |
16 |
Correct |
14 ms |
27728 KB |
Output is correct |
17 |
Correct |
14 ms |
27740 KB |
Output is correct |
18 |
Correct |
13 ms |
27664 KB |
Output is correct |
19 |
Correct |
14 ms |
27728 KB |
Output is correct |
20 |
Correct |
13 ms |
27728 KB |
Output is correct |
21 |
Correct |
14 ms |
27680 KB |
Output is correct |
22 |
Correct |
13 ms |
27740 KB |
Output is correct |
23 |
Correct |
14 ms |
27640 KB |
Output is correct |
24 |
Correct |
14 ms |
27664 KB |
Output is correct |
25 |
Correct |
14 ms |
27744 KB |
Output is correct |
26 |
Correct |
15 ms |
27768 KB |
Output is correct |
27 |
Correct |
15 ms |
27744 KB |
Output is correct |
28 |
Correct |
14 ms |
27748 KB |
Output is correct |
29 |
Correct |
14 ms |
27744 KB |
Output is correct |
30 |
Correct |
14 ms |
27856 KB |
Output is correct |
31 |
Correct |
14 ms |
27728 KB |
Output is correct |
32 |
Correct |
14 ms |
27748 KB |
Output is correct |
33 |
Correct |
15 ms |
27784 KB |
Output is correct |
34 |
Correct |
14 ms |
27752 KB |
Output is correct |
35 |
Correct |
14 ms |
27752 KB |
Output is correct |
36 |
Correct |
14 ms |
27728 KB |
Output is correct |
37 |
Correct |
15 ms |
27840 KB |
Output is correct |
38 |
Correct |
14 ms |
27856 KB |
Output is correct |
39 |
Correct |
14 ms |
27856 KB |
Output is correct |
40 |
Correct |
15 ms |
27728 KB |
Output is correct |
41 |
Correct |
14 ms |
27828 KB |
Output is correct |
42 |
Correct |
15 ms |
27856 KB |
Output is correct |
43 |
Correct |
15 ms |
27916 KB |
Output is correct |
44 |
Correct |
15 ms |
27884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
27740 KB |
Output is correct |
2 |
Correct |
13 ms |
27712 KB |
Output is correct |
3 |
Correct |
13 ms |
27680 KB |
Output is correct |
4 |
Correct |
14 ms |
27728 KB |
Output is correct |
5 |
Correct |
13 ms |
27728 KB |
Output is correct |
6 |
Correct |
13 ms |
27728 KB |
Output is correct |
7 |
Correct |
13 ms |
27664 KB |
Output is correct |
8 |
Correct |
13 ms |
27728 KB |
Output is correct |
9 |
Correct |
13 ms |
27728 KB |
Output is correct |
10 |
Correct |
15 ms |
27728 KB |
Output is correct |
11 |
Correct |
14 ms |
27732 KB |
Output is correct |
12 |
Correct |
14 ms |
27700 KB |
Output is correct |
13 |
Correct |
13 ms |
27664 KB |
Output is correct |
14 |
Correct |
14 ms |
27728 KB |
Output is correct |
15 |
Correct |
15 ms |
27684 KB |
Output is correct |
16 |
Correct |
14 ms |
27728 KB |
Output is correct |
17 |
Correct |
14 ms |
27740 KB |
Output is correct |
18 |
Correct |
13 ms |
27664 KB |
Output is correct |
19 |
Correct |
14 ms |
27728 KB |
Output is correct |
20 |
Correct |
13 ms |
27728 KB |
Output is correct |
21 |
Correct |
14 ms |
27680 KB |
Output is correct |
22 |
Correct |
13 ms |
27740 KB |
Output is correct |
23 |
Correct |
14 ms |
27640 KB |
Output is correct |
24 |
Correct |
14 ms |
27664 KB |
Output is correct |
25 |
Correct |
14 ms |
27744 KB |
Output is correct |
26 |
Correct |
15 ms |
27768 KB |
Output is correct |
27 |
Correct |
15 ms |
27744 KB |
Output is correct |
28 |
Correct |
14 ms |
27748 KB |
Output is correct |
29 |
Correct |
14 ms |
27744 KB |
Output is correct |
30 |
Correct |
14 ms |
27856 KB |
Output is correct |
31 |
Correct |
14 ms |
27728 KB |
Output is correct |
32 |
Correct |
14 ms |
27748 KB |
Output is correct |
33 |
Correct |
15 ms |
27784 KB |
Output is correct |
34 |
Correct |
14 ms |
27752 KB |
Output is correct |
35 |
Correct |
14 ms |
27752 KB |
Output is correct |
36 |
Correct |
14 ms |
27728 KB |
Output is correct |
37 |
Correct |
15 ms |
27840 KB |
Output is correct |
38 |
Correct |
14 ms |
27856 KB |
Output is correct |
39 |
Correct |
14 ms |
27856 KB |
Output is correct |
40 |
Correct |
15 ms |
27728 KB |
Output is correct |
41 |
Correct |
14 ms |
27828 KB |
Output is correct |
42 |
Correct |
15 ms |
27856 KB |
Output is correct |
43 |
Correct |
15 ms |
27916 KB |
Output is correct |
44 |
Correct |
15 ms |
27884 KB |
Output is correct |
45 |
Correct |
54 ms |
33596 KB |
Output is correct |
46 |
Correct |
55 ms |
33560 KB |
Output is correct |
47 |
Correct |
54 ms |
33608 KB |
Output is correct |
48 |
Correct |
57 ms |
33880 KB |
Output is correct |
49 |
Correct |
54 ms |
33616 KB |
Output is correct |
50 |
Correct |
47 ms |
33352 KB |
Output is correct |
51 |
Correct |
46 ms |
33356 KB |
Output is correct |
52 |
Correct |
34 ms |
31140 KB |
Output is correct |
53 |
Correct |
35 ms |
31180 KB |
Output is correct |
54 |
Correct |
55 ms |
37732 KB |
Output is correct |
55 |
Correct |
53 ms |
36444 KB |
Output is correct |
56 |
Correct |
64 ms |
36628 KB |
Output is correct |
57 |
Correct |
52 ms |
34008 KB |
Output is correct |
58 |
Correct |
36 ms |
30828 KB |
Output is correct |
59 |
Correct |
44 ms |
31328 KB |
Output is correct |
60 |
Correct |
57 ms |
32736 KB |
Output is correct |
61 |
Correct |
54 ms |
33392 KB |
Output is correct |
62 |
Correct |
42 ms |
32328 KB |
Output is correct |
63 |
Correct |
49 ms |
32716 KB |
Output is correct |
64 |
Correct |
45 ms |
33104 KB |
Output is correct |
65 |
Correct |
56 ms |
34860 KB |
Output is correct |
66 |
Correct |
61 ms |
34760 KB |
Output is correct |
67 |
Correct |
45 ms |
34644 KB |
Output is correct |
68 |
Correct |
48 ms |
34732 KB |
Output is correct |
69 |
Correct |
47 ms |
35024 KB |
Output is correct |
70 |
Correct |
47 ms |
35016 KB |
Output is correct |
71 |
Correct |
53 ms |
34708 KB |
Output is correct |
72 |
Correct |
45 ms |
34632 KB |
Output is correct |
73 |
Correct |
47 ms |
35048 KB |
Output is correct |
74 |
Correct |
46 ms |
35024 KB |
Output is correct |
75 |
Correct |
54 ms |
36800 KB |
Output is correct |
76 |
Correct |
54 ms |
38688 KB |
Output is correct |
77 |
Correct |
52 ms |
38724 KB |
Output is correct |
78 |
Correct |
52 ms |
33608 KB |
Output is correct |
79 |
Correct |
51 ms |
33520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
27740 KB |
Output is correct |
2 |
Correct |
13 ms |
27712 KB |
Output is correct |
3 |
Correct |
13 ms |
27680 KB |
Output is correct |
4 |
Correct |
14 ms |
27728 KB |
Output is correct |
5 |
Correct |
13 ms |
27728 KB |
Output is correct |
6 |
Correct |
13 ms |
27728 KB |
Output is correct |
7 |
Correct |
13 ms |
27664 KB |
Output is correct |
8 |
Correct |
13 ms |
27728 KB |
Output is correct |
9 |
Correct |
13 ms |
27728 KB |
Output is correct |
10 |
Correct |
15 ms |
27728 KB |
Output is correct |
11 |
Correct |
14 ms |
27732 KB |
Output is correct |
12 |
Correct |
14 ms |
27700 KB |
Output is correct |
13 |
Correct |
13 ms |
27664 KB |
Output is correct |
14 |
Correct |
14 ms |
27728 KB |
Output is correct |
15 |
Correct |
15 ms |
27684 KB |
Output is correct |
16 |
Correct |
14 ms |
27728 KB |
Output is correct |
17 |
Correct |
14 ms |
27740 KB |
Output is correct |
18 |
Correct |
13 ms |
27664 KB |
Output is correct |
19 |
Correct |
14 ms |
27728 KB |
Output is correct |
20 |
Correct |
13 ms |
27728 KB |
Output is correct |
21 |
Correct |
14 ms |
27680 KB |
Output is correct |
22 |
Correct |
13 ms |
27740 KB |
Output is correct |
23 |
Correct |
14 ms |
27640 KB |
Output is correct |
24 |
Correct |
14 ms |
27664 KB |
Output is correct |
25 |
Correct |
14 ms |
27744 KB |
Output is correct |
26 |
Correct |
15 ms |
27768 KB |
Output is correct |
27 |
Correct |
15 ms |
27744 KB |
Output is correct |
28 |
Correct |
14 ms |
27748 KB |
Output is correct |
29 |
Correct |
14 ms |
27744 KB |
Output is correct |
30 |
Correct |
14 ms |
27856 KB |
Output is correct |
31 |
Correct |
14 ms |
27728 KB |
Output is correct |
32 |
Correct |
14 ms |
27748 KB |
Output is correct |
33 |
Correct |
15 ms |
27784 KB |
Output is correct |
34 |
Correct |
14 ms |
27752 KB |
Output is correct |
35 |
Correct |
14 ms |
27752 KB |
Output is correct |
36 |
Correct |
14 ms |
27728 KB |
Output is correct |
37 |
Correct |
15 ms |
27840 KB |
Output is correct |
38 |
Correct |
14 ms |
27856 KB |
Output is correct |
39 |
Correct |
14 ms |
27856 KB |
Output is correct |
40 |
Correct |
15 ms |
27728 KB |
Output is correct |
41 |
Correct |
14 ms |
27828 KB |
Output is correct |
42 |
Correct |
15 ms |
27856 KB |
Output is correct |
43 |
Correct |
15 ms |
27916 KB |
Output is correct |
44 |
Correct |
15 ms |
27884 KB |
Output is correct |
45 |
Correct |
54 ms |
33596 KB |
Output is correct |
46 |
Correct |
55 ms |
33560 KB |
Output is correct |
47 |
Correct |
54 ms |
33608 KB |
Output is correct |
48 |
Correct |
57 ms |
33880 KB |
Output is correct |
49 |
Correct |
54 ms |
33616 KB |
Output is correct |
50 |
Correct |
47 ms |
33352 KB |
Output is correct |
51 |
Correct |
46 ms |
33356 KB |
Output is correct |
52 |
Correct |
34 ms |
31140 KB |
Output is correct |
53 |
Correct |
35 ms |
31180 KB |
Output is correct |
54 |
Correct |
55 ms |
37732 KB |
Output is correct |
55 |
Correct |
53 ms |
36444 KB |
Output is correct |
56 |
Correct |
64 ms |
36628 KB |
Output is correct |
57 |
Correct |
52 ms |
34008 KB |
Output is correct |
58 |
Correct |
36 ms |
30828 KB |
Output is correct |
59 |
Correct |
44 ms |
31328 KB |
Output is correct |
60 |
Correct |
57 ms |
32736 KB |
Output is correct |
61 |
Correct |
54 ms |
33392 KB |
Output is correct |
62 |
Correct |
42 ms |
32328 KB |
Output is correct |
63 |
Correct |
49 ms |
32716 KB |
Output is correct |
64 |
Correct |
45 ms |
33104 KB |
Output is correct |
65 |
Correct |
56 ms |
34860 KB |
Output is correct |
66 |
Correct |
61 ms |
34760 KB |
Output is correct |
67 |
Correct |
45 ms |
34644 KB |
Output is correct |
68 |
Correct |
48 ms |
34732 KB |
Output is correct |
69 |
Correct |
47 ms |
35024 KB |
Output is correct |
70 |
Correct |
47 ms |
35016 KB |
Output is correct |
71 |
Correct |
53 ms |
34708 KB |
Output is correct |
72 |
Correct |
45 ms |
34632 KB |
Output is correct |
73 |
Correct |
47 ms |
35048 KB |
Output is correct |
74 |
Correct |
46 ms |
35024 KB |
Output is correct |
75 |
Correct |
54 ms |
36800 KB |
Output is correct |
76 |
Correct |
54 ms |
38688 KB |
Output is correct |
77 |
Correct |
52 ms |
38724 KB |
Output is correct |
78 |
Correct |
52 ms |
33608 KB |
Output is correct |
79 |
Correct |
51 ms |
33520 KB |
Output is correct |
80 |
Correct |
768 ms |
87760 KB |
Output is correct |
81 |
Correct |
728 ms |
87912 KB |
Output is correct |
82 |
Correct |
732 ms |
88248 KB |
Output is correct |
83 |
Correct |
732 ms |
88356 KB |
Output is correct |
84 |
Correct |
718 ms |
88172 KB |
Output is correct |
85 |
Correct |
684 ms |
85828 KB |
Output is correct |
86 |
Correct |
667 ms |
85564 KB |
Output is correct |
87 |
Correct |
327 ms |
62144 KB |
Output is correct |
88 |
Correct |
330 ms |
62156 KB |
Output is correct |
89 |
Correct |
835 ms |
123776 KB |
Output is correct |
90 |
Correct |
832 ms |
117960 KB |
Output is correct |
91 |
Correct |
811 ms |
115608 KB |
Output is correct |
92 |
Correct |
726 ms |
93044 KB |
Output is correct |
93 |
Correct |
302 ms |
60048 KB |
Output is correct |
94 |
Correct |
550 ms |
73452 KB |
Output is correct |
95 |
Correct |
712 ms |
84712 KB |
Output is correct |
96 |
Correct |
751 ms |
86908 KB |
Output is correct |
97 |
Correct |
474 ms |
74948 KB |
Output is correct |
98 |
Correct |
648 ms |
83432 KB |
Output is correct |
99 |
Correct |
602 ms |
86176 KB |
Output is correct |
100 |
Correct |
836 ms |
100964 KB |
Output is correct |
101 |
Correct |
918 ms |
100900 KB |
Output is correct |
102 |
Correct |
590 ms |
98184 KB |
Output is correct |
103 |
Correct |
602 ms |
98324 KB |
Output is correct |
104 |
Correct |
677 ms |
101152 KB |
Output is correct |
105 |
Correct |
685 ms |
101144 KB |
Output is correct |
106 |
Correct |
613 ms |
98088 KB |
Output is correct |
107 |
Correct |
582 ms |
98272 KB |
Output is correct |
108 |
Correct |
673 ms |
101208 KB |
Output is correct |
109 |
Correct |
640 ms |
101248 KB |
Output is correct |
110 |
Correct |
868 ms |
139132 KB |
Output is correct |
111 |
Correct |
879 ms |
140104 KB |
Output is correct |
112 |
Correct |
830 ms |
140048 KB |
Output is correct |
113 |
Correct |
733 ms |
88468 KB |
Output is correct |
114 |
Correct |
757 ms |
88416 KB |
Output is correct |