#include <bits/stdc++.h>
/*
Entre tanta gente yo te vi llegar
Algo en el destino me hizo saludar
Te dije me nombre e no sé dónde
Como con un beso me respondes
*/
#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
const int MAX = 2e6+10 ;
const int MOD = 1e9+7 ;
using namespace std ;
int N ;
int L[MAX] , R[MAX] ;
int saveL[MAX], saveR[MAX] ;
int beginsHere[MAX], endsHere[MAX] ;
struct Seg
{
//Seg zero means I'm searching i s.t. L[i] < L
int type ;
int tree[MAX*4] ;
int m(int l, int r ) { return (l+r)>>1 ; }
int merge(int type , int lef, int rig)
{
if( !type ) return ( L[lef ]< L[rig] ) ? lef : rig ;
return (R[lef] >R[rig] ) ? lef : rig ;
}
void build(int pos, int l, int r )
{
if( l == r )
{
tree[pos] = type ? beginsHere[l] : endsHere[r] ;
return ;
}
build(pos<<1 , l , m(l,r) ) ;
build(pos<<1|1 , m(l,r)+1, r ) ;
tree[pos] = merge(type, tree[pos<<1], tree[pos<<1|1] ) ;
}
void makeRemoval(int pos, int l, int r, int x )
{
if( l == r ) return ;
if( x <= m(l,r) ) makeRemoval(pos<<1 , l , m(l,r) , x ) ;
else makeRemoval(pos<<1|1 , m(l,r)+1, r, x ) ;
tree[pos] = merge(type, tree[pos<<1], tree[pos<<1|1] ) ;
}
int qry(int pos, int l, int r, int beg, int en )
{
// debug("%d %d and look for %d %d and ans %d\n", l, r, beg, en, tree[pos] ) ;
if( l > en || r < beg ) return 0 ;
if( l >= beg && r <= en ) return tree[pos] ;
int al = qry(pos<<1 , l , m(l,r) , beg, en ) ;
int ar = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;
return merge(type, al, ar ) ;
}
} seg[2] ;
int main()
{
seg[0].type = 0 ;
seg[1].type = 1 ;
scanf("%d", &N ) ;
for(int i= 1 ; i <= N ; i++ )
{
scanf("%d %d", &L[i] , &R[i] ) ;
saveL[i] = L[i] ; saveR[i] = R[i] ;
beginsHere[ L[i] ] = i ;
endsHere[ R[i] ] = i ;
}
L[0] = 2*N+1 ;
R[0] = -1 ;
seg[0].build(1,1,2*N) ;
seg[1].build(1,1,2*N) ;
vector<int> color(N+1,-1) ;
color[0] = 0 ;
int ans= 1 ;
for(int i= 1 ; i <= N ; i++ )
{
if( color[i] != -1 ) continue ;
ans <<= 1 ;
if(ans >= MOD ) ans -= MOD ;
vector<int> fila(1,i) ;
color[i] = 0 ;
int ini = 0 ;
L[i] = 2*N+1 ;
R[i] = -1 ;
seg[0].makeRemoval(1,1,2*N, saveR[i] ) ;
seg[1].makeRemoval(1,1,2*N, saveL[i] ) ;
while( ini < sz(fila) )
{
int x = fila[ini++] ;
int y;
for(int j = 0 ; j < 2 ; j++ )
{
y = seg[j].qry(1,1,2*N, saveL[x] , saveR[x] ) ;
while( color[y] == -1 && ( (!j && L[y] < saveL[x]) || (j && R[y] > saveR[x] ) ) )
{
color[y] = !color[x] ;
L[y] = 2*N+1 ;
R[y] = -1 ;
seg[0].makeRemoval(1,1,2*N, saveR[y] ) ;
seg[1].makeRemoval(1,1,2*N, saveL[y] ) ;
fila.push_back(y) ;
y = seg[j].qry( 1, 1, 2*N, saveL[x], saveR[x] ) ;
}
}
}
}
vector<int> toSort(N) ; iota(all(toSort),1) ;
sort( all(toSort), [&](int i, int j) { return saveL[i] < saveL[j] ; } ) ;
set<int> s[2] ;
for(auto e : toSort )
{
int c = color[e] ;
auto it = s[c].upper_bound(saveR[e]) ;
if(it != s[c].begin() )
{
it-- ;
if( *it > saveL[e] )
{
printf("0\n" ) ;
return 0 ;
}
}
s[c].insert(saveR[e] ) ;
}
printf("%d\n", ans ) ;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
88 | scanf("%d", &N ) ;
| ~~~~~^~~~~~~~~~~
port_facility.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
91 | scanf("%d %d", &L[i] , &R[i] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
388 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
388 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
3 ms |
620 KB |
Output is correct |
26 |
Correct |
3 ms |
620 KB |
Output is correct |
27 |
Correct |
4 ms |
620 KB |
Output is correct |
28 |
Correct |
4 ms |
620 KB |
Output is correct |
29 |
Correct |
4 ms |
620 KB |
Output is correct |
30 |
Correct |
4 ms |
620 KB |
Output is correct |
31 |
Correct |
4 ms |
620 KB |
Output is correct |
32 |
Correct |
4 ms |
620 KB |
Output is correct |
33 |
Correct |
3 ms |
620 KB |
Output is correct |
34 |
Correct |
3 ms |
492 KB |
Output is correct |
35 |
Correct |
3 ms |
620 KB |
Output is correct |
36 |
Correct |
3 ms |
620 KB |
Output is correct |
37 |
Correct |
3 ms |
492 KB |
Output is correct |
38 |
Correct |
3 ms |
492 KB |
Output is correct |
39 |
Correct |
3 ms |
620 KB |
Output is correct |
40 |
Correct |
4 ms |
620 KB |
Output is correct |
41 |
Correct |
3 ms |
620 KB |
Output is correct |
42 |
Correct |
3 ms |
620 KB |
Output is correct |
43 |
Correct |
3 ms |
620 KB |
Output is correct |
44 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
388 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
3 ms |
620 KB |
Output is correct |
26 |
Correct |
3 ms |
620 KB |
Output is correct |
27 |
Correct |
4 ms |
620 KB |
Output is correct |
28 |
Correct |
4 ms |
620 KB |
Output is correct |
29 |
Correct |
4 ms |
620 KB |
Output is correct |
30 |
Correct |
4 ms |
620 KB |
Output is correct |
31 |
Correct |
4 ms |
620 KB |
Output is correct |
32 |
Correct |
4 ms |
620 KB |
Output is correct |
33 |
Correct |
3 ms |
620 KB |
Output is correct |
34 |
Correct |
3 ms |
492 KB |
Output is correct |
35 |
Correct |
3 ms |
620 KB |
Output is correct |
36 |
Correct |
3 ms |
620 KB |
Output is correct |
37 |
Correct |
3 ms |
492 KB |
Output is correct |
38 |
Correct |
3 ms |
492 KB |
Output is correct |
39 |
Correct |
3 ms |
620 KB |
Output is correct |
40 |
Correct |
4 ms |
620 KB |
Output is correct |
41 |
Correct |
3 ms |
620 KB |
Output is correct |
42 |
Correct |
3 ms |
620 KB |
Output is correct |
43 |
Correct |
3 ms |
620 KB |
Output is correct |
44 |
Correct |
3 ms |
620 KB |
Output is correct |
45 |
Correct |
243 ms |
13132 KB |
Output is correct |
46 |
Correct |
210 ms |
13152 KB |
Output is correct |
47 |
Correct |
232 ms |
13244 KB |
Output is correct |
48 |
Correct |
213 ms |
13116 KB |
Output is correct |
49 |
Correct |
210 ms |
13164 KB |
Output is correct |
50 |
Correct |
184 ms |
9452 KB |
Output is correct |
51 |
Correct |
191 ms |
10592 KB |
Output is correct |
52 |
Correct |
187 ms |
13164 KB |
Output is correct |
53 |
Correct |
225 ms |
12396 KB |
Output is correct |
54 |
Correct |
178 ms |
8168 KB |
Output is correct |
55 |
Correct |
173 ms |
8060 KB |
Output is correct |
56 |
Correct |
165 ms |
7776 KB |
Output is correct |
57 |
Correct |
203 ms |
13164 KB |
Output is correct |
58 |
Correct |
189 ms |
13164 KB |
Output is correct |
59 |
Correct |
222 ms |
13164 KB |
Output is correct |
60 |
Correct |
248 ms |
13212 KB |
Output is correct |
61 |
Correct |
214 ms |
13164 KB |
Output is correct |
62 |
Correct |
171 ms |
8548 KB |
Output is correct |
63 |
Correct |
203 ms |
8848 KB |
Output is correct |
64 |
Correct |
183 ms |
8868 KB |
Output is correct |
65 |
Correct |
201 ms |
8400 KB |
Output is correct |
66 |
Correct |
207 ms |
8424 KB |
Output is correct |
67 |
Correct |
204 ms |
12920 KB |
Output is correct |
68 |
Correct |
216 ms |
12892 KB |
Output is correct |
69 |
Correct |
192 ms |
12792 KB |
Output is correct |
70 |
Correct |
219 ms |
12776 KB |
Output is correct |
71 |
Correct |
193 ms |
12380 KB |
Output is correct |
72 |
Correct |
184 ms |
12536 KB |
Output is correct |
73 |
Correct |
189 ms |
12380 KB |
Output is correct |
74 |
Correct |
194 ms |
12380 KB |
Output is correct |
75 |
Correct |
190 ms |
13148 KB |
Output is correct |
76 |
Correct |
174 ms |
13148 KB |
Output is correct |
77 |
Correct |
170 ms |
11740 KB |
Output is correct |
78 |
Correct |
206 ms |
13264 KB |
Output is correct |
79 |
Correct |
220 ms |
13224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
388 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
3 ms |
620 KB |
Output is correct |
26 |
Correct |
3 ms |
620 KB |
Output is correct |
27 |
Correct |
4 ms |
620 KB |
Output is correct |
28 |
Correct |
4 ms |
620 KB |
Output is correct |
29 |
Correct |
4 ms |
620 KB |
Output is correct |
30 |
Correct |
4 ms |
620 KB |
Output is correct |
31 |
Correct |
4 ms |
620 KB |
Output is correct |
32 |
Correct |
4 ms |
620 KB |
Output is correct |
33 |
Correct |
3 ms |
620 KB |
Output is correct |
34 |
Correct |
3 ms |
492 KB |
Output is correct |
35 |
Correct |
3 ms |
620 KB |
Output is correct |
36 |
Correct |
3 ms |
620 KB |
Output is correct |
37 |
Correct |
3 ms |
492 KB |
Output is correct |
38 |
Correct |
3 ms |
492 KB |
Output is correct |
39 |
Correct |
3 ms |
620 KB |
Output is correct |
40 |
Correct |
4 ms |
620 KB |
Output is correct |
41 |
Correct |
3 ms |
620 KB |
Output is correct |
42 |
Correct |
3 ms |
620 KB |
Output is correct |
43 |
Correct |
3 ms |
620 KB |
Output is correct |
44 |
Correct |
3 ms |
620 KB |
Output is correct |
45 |
Correct |
243 ms |
13132 KB |
Output is correct |
46 |
Correct |
210 ms |
13152 KB |
Output is correct |
47 |
Correct |
232 ms |
13244 KB |
Output is correct |
48 |
Correct |
213 ms |
13116 KB |
Output is correct |
49 |
Correct |
210 ms |
13164 KB |
Output is correct |
50 |
Correct |
184 ms |
9452 KB |
Output is correct |
51 |
Correct |
191 ms |
10592 KB |
Output is correct |
52 |
Correct |
187 ms |
13164 KB |
Output is correct |
53 |
Correct |
225 ms |
12396 KB |
Output is correct |
54 |
Correct |
178 ms |
8168 KB |
Output is correct |
55 |
Correct |
173 ms |
8060 KB |
Output is correct |
56 |
Correct |
165 ms |
7776 KB |
Output is correct |
57 |
Correct |
203 ms |
13164 KB |
Output is correct |
58 |
Correct |
189 ms |
13164 KB |
Output is correct |
59 |
Correct |
222 ms |
13164 KB |
Output is correct |
60 |
Correct |
248 ms |
13212 KB |
Output is correct |
61 |
Correct |
214 ms |
13164 KB |
Output is correct |
62 |
Correct |
171 ms |
8548 KB |
Output is correct |
63 |
Correct |
203 ms |
8848 KB |
Output is correct |
64 |
Correct |
183 ms |
8868 KB |
Output is correct |
65 |
Correct |
201 ms |
8400 KB |
Output is correct |
66 |
Correct |
207 ms |
8424 KB |
Output is correct |
67 |
Correct |
204 ms |
12920 KB |
Output is correct |
68 |
Correct |
216 ms |
12892 KB |
Output is correct |
69 |
Correct |
192 ms |
12792 KB |
Output is correct |
70 |
Correct |
219 ms |
12776 KB |
Output is correct |
71 |
Correct |
193 ms |
12380 KB |
Output is correct |
72 |
Correct |
184 ms |
12536 KB |
Output is correct |
73 |
Correct |
189 ms |
12380 KB |
Output is correct |
74 |
Correct |
194 ms |
12380 KB |
Output is correct |
75 |
Correct |
190 ms |
13148 KB |
Output is correct |
76 |
Correct |
174 ms |
13148 KB |
Output is correct |
77 |
Correct |
170 ms |
11740 KB |
Output is correct |
78 |
Correct |
206 ms |
13264 KB |
Output is correct |
79 |
Correct |
220 ms |
13224 KB |
Output is correct |
80 |
Correct |
3072 ms |
119384 KB |
Output is correct |
81 |
Correct |
3118 ms |
119404 KB |
Output is correct |
82 |
Correct |
3013 ms |
119400 KB |
Output is correct |
83 |
Correct |
3022 ms |
119292 KB |
Output is correct |
84 |
Correct |
3097 ms |
119392 KB |
Output is correct |
85 |
Correct |
2709 ms |
90568 KB |
Output is correct |
86 |
Correct |
2852 ms |
96372 KB |
Output is correct |
87 |
Correct |
2879 ms |
119404 KB |
Output is correct |
88 |
Correct |
3708 ms |
111468 KB |
Output is correct |
89 |
Correct |
2435 ms |
64972 KB |
Output is correct |
90 |
Correct |
2513 ms |
64656 KB |
Output is correct |
91 |
Correct |
2482 ms |
64656 KB |
Output is correct |
92 |
Correct |
2916 ms |
119288 KB |
Output is correct |
93 |
Correct |
2964 ms |
119448 KB |
Output is correct |
94 |
Correct |
3398 ms |
119532 KB |
Output is correct |
95 |
Correct |
3171 ms |
119404 KB |
Output is correct |
96 |
Correct |
2945 ms |
119404 KB |
Output is correct |
97 |
Correct |
2933 ms |
85408 KB |
Output is correct |
98 |
Correct |
2919 ms |
91716 KB |
Output is correct |
99 |
Correct |
2600 ms |
78816 KB |
Output is correct |
100 |
Correct |
3544 ms |
69108 KB |
Output is correct |
101 |
Correct |
3483 ms |
83444 KB |
Output is correct |
102 |
Correct |
2935 ms |
130220 KB |
Output is correct |
103 |
Correct |
2776 ms |
130200 KB |
Output is correct |
104 |
Correct |
2892 ms |
130116 KB |
Output is correct |
105 |
Correct |
2891 ms |
130192 KB |
Output is correct |
106 |
Correct |
2851 ms |
126020 KB |
Output is correct |
107 |
Correct |
2762 ms |
126668 KB |
Output is correct |
108 |
Correct |
2810 ms |
126340 KB |
Output is correct |
109 |
Correct |
2804 ms |
126252 KB |
Output is correct |
110 |
Correct |
2492 ms |
133904 KB |
Output is correct |
111 |
Correct |
2576 ms |
133888 KB |
Output is correct |
112 |
Correct |
2375 ms |
122440 KB |
Output is correct |
113 |
Correct |
2989 ms |
133932 KB |
Output is correct |
114 |
Correct |
3012 ms |
133920 KB |
Output is correct |