#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef pair < int, int > pii;
const int N = 2e6 + 500;
const int MOD = 1e9 + 7;
vector < pii > v[N];
int col[N], bio[N], mog = 1, n;
int L[N], R[N], id[N], str[N];
int ima[N], stvar[N];
void dodaj(int x,int y,int razl = 1){
//printf("%d --%d-- %d\n", x, razl, y);
v[x].PB({y, razl});
v[y].PB({x, razl});
}
void dfs(int x){
if(bio[x]) return;
bio[x] = 1;
for(pii nxt : v[x]){
if(bio[nxt.X] && (col[x] ^ col[nxt.X]) != nxt.Y)
mog = 0;
if(!bio[nxt.X]){
col[nxt.X] = col[x] ^ nxt.Y;
dfs(nxt.X);
}
}
}
inline bool inter(int i,int j){
if(i == j) return 0;
if(L[i] < L[j] && R[i] < R[j] && R[i] > L[j])
return 1;
if(L[i] > L[j] && R[i] > R[j] && R[j] > L[i])
return 1;
return 0;
}
void obradi(int l,int r){
if(l >= r) return;
//printf("l = %d r = %d\n", l, r);
int mid = (l + r) / 2;
int lst = -1, cnt = 0, pos = 0;
vector < int > sljed;
// RIJESI SVE PREMA DESNO
for(int i = mid + 1;i <= r;i++){
if(L[id[i]] < l || R[id[i]] > r) continue;
if(str[i]){
if(L[id[i]] <= mid){
if(lst != -1 && cnt)
dodaj(id[i], lst, 0);
lst = id[i];
for(int x : sljed){
if(inter(lst, x))
dodaj(lst, x, 1);
}
sljed.clear();
cnt += pos; pos = 0;
}
else if(lst == -1 || L[id[i]] > R[lst])
pos--;
else
cnt--;
}
else{
sljed.PB(id[i]);
pos++;
}
//printf("cnt = %d pos = %d i = %d\n", cnt, pos, i);
}
//printf("rijesio desno\n");
lst = -1, cnt = 0, pos = 0;
sljed.clear();
// RIJESI SVE PREMA LIJEVO
for(int i = mid;i >= l;i--){
if(L[id[i]] < l || R[id[i]] > r) continue;
if(!str[i]){
if(R[id[i]] > mid){
if(lst != -1 && cnt)
dodaj(id[i], lst, 0);
lst = id[i];
for(int x : sljed){
if(inter(lst, x))
dodaj(lst, x, 1);
}
sljed.clear();
cnt += pos; pos = 0;
}
else if(lst == -1 || R[id[i]] < L[lst])
pos--;
else
cnt--;
}
else{
sljed.PB(id[i]);
pos++;
}
}
//printf("rijesio lijevo\n");
// RIJESI SVE KOJI SIJEKU
vector < int > niz;
for(int i = l;i <= mid;i++){
if(L[id[i]] < l || R[id[i]] > r) continue;
if(R[id[i]] > mid){
niz.PB(id[i]);
}
}
int cur = (int)niz.size();
for(int i = mid + 1;i <= r;i++){
if(L[id[i]] < l || R[id[i]] > r) continue;
if(L[id[i]] <= mid)
stvar[id[i]] = cur--;
}
stack < int > svi;
int zad = 1;int mx = -1;
for(int x : niz){
//printf("x = %d stvar[ %d ] = %d\n", x, x, stvar[x]);
if(mx != -1 && stvar[mx] > zad && stvar[x] > zad)
dodaj(mx, x, 0);
if(mx == -1 || stvar[x] > stvar[mx]){
mx = x;
}
if(mx != x)
dodaj(x, mx, 1);
ima[stvar[x]]++;
while(ima[zad])
zad++;
//while(!svi.empty() && stvar[svi.top()] < stvar[x]){
// if(stvar[svi.top()] > zad && stvar[x] > zad)
// dodaj(svi.top(), x, 0);
// svi.pop();
//}
//svi.push(x);
}
//printf("rijesio sredinu\n");
for(int i = 0;i <= (int)niz.size();i++)
ima[i] = 0;
obradi(l, mid); obradi(mid + 1, r);
}
int main(){
scanf("%d", &n);
for(int i = 1;i <= n;i++){
scanf("%d%d", L + i, R + i);
id[L[i]] = i, id[R[i]] = i;
str[R[i]] = 1;
}
obradi(1, 2 * n);
int komp = 0;
for(int i = 1;i <= n;i++){
komp += !bio[i]; dfs(i);
}
int sol = 1;
for(;komp--;) sol = (sol + sol) % MOD;
printf("%d\n", sol * mog);
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:154:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
port_facility.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", L + i, R + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47360 KB |
Output is correct |
2 |
Correct |
28 ms |
47360 KB |
Output is correct |
3 |
Correct |
28 ms |
47360 KB |
Output is correct |
4 |
Correct |
28 ms |
47360 KB |
Output is correct |
5 |
Correct |
28 ms |
47360 KB |
Output is correct |
6 |
Correct |
28 ms |
47360 KB |
Output is correct |
7 |
Correct |
28 ms |
47224 KB |
Output is correct |
8 |
Correct |
28 ms |
47360 KB |
Output is correct |
9 |
Correct |
28 ms |
47232 KB |
Output is correct |
10 |
Correct |
28 ms |
47360 KB |
Output is correct |
11 |
Correct |
28 ms |
47360 KB |
Output is correct |
12 |
Correct |
29 ms |
47360 KB |
Output is correct |
13 |
Correct |
29 ms |
47360 KB |
Output is correct |
14 |
Correct |
29 ms |
47360 KB |
Output is correct |
15 |
Correct |
28 ms |
47360 KB |
Output is correct |
16 |
Correct |
29 ms |
47344 KB |
Output is correct |
17 |
Correct |
29 ms |
47232 KB |
Output is correct |
18 |
Correct |
28 ms |
47352 KB |
Output is correct |
19 |
Correct |
29 ms |
47360 KB |
Output is correct |
20 |
Correct |
30 ms |
47352 KB |
Output is correct |
21 |
Correct |
29 ms |
47360 KB |
Output is correct |
22 |
Correct |
29 ms |
47360 KB |
Output is correct |
23 |
Correct |
28 ms |
47232 KB |
Output is correct |
24 |
Correct |
29 ms |
47360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47360 KB |
Output is correct |
2 |
Correct |
28 ms |
47360 KB |
Output is correct |
3 |
Correct |
28 ms |
47360 KB |
Output is correct |
4 |
Correct |
28 ms |
47360 KB |
Output is correct |
5 |
Correct |
28 ms |
47360 KB |
Output is correct |
6 |
Correct |
28 ms |
47360 KB |
Output is correct |
7 |
Correct |
28 ms |
47224 KB |
Output is correct |
8 |
Correct |
28 ms |
47360 KB |
Output is correct |
9 |
Correct |
28 ms |
47232 KB |
Output is correct |
10 |
Correct |
28 ms |
47360 KB |
Output is correct |
11 |
Correct |
28 ms |
47360 KB |
Output is correct |
12 |
Correct |
29 ms |
47360 KB |
Output is correct |
13 |
Correct |
29 ms |
47360 KB |
Output is correct |
14 |
Correct |
29 ms |
47360 KB |
Output is correct |
15 |
Correct |
28 ms |
47360 KB |
Output is correct |
16 |
Correct |
29 ms |
47344 KB |
Output is correct |
17 |
Correct |
29 ms |
47232 KB |
Output is correct |
18 |
Correct |
28 ms |
47352 KB |
Output is correct |
19 |
Correct |
29 ms |
47360 KB |
Output is correct |
20 |
Correct |
30 ms |
47352 KB |
Output is correct |
21 |
Correct |
29 ms |
47360 KB |
Output is correct |
22 |
Correct |
29 ms |
47360 KB |
Output is correct |
23 |
Correct |
28 ms |
47232 KB |
Output is correct |
24 |
Correct |
29 ms |
47360 KB |
Output is correct |
25 |
Correct |
30 ms |
47616 KB |
Output is correct |
26 |
Correct |
31 ms |
47488 KB |
Output is correct |
27 |
Correct |
32 ms |
47488 KB |
Output is correct |
28 |
Correct |
31 ms |
47488 KB |
Output is correct |
29 |
Correct |
31 ms |
47488 KB |
Output is correct |
30 |
Correct |
32 ms |
47488 KB |
Output is correct |
31 |
Correct |
32 ms |
47480 KB |
Output is correct |
32 |
Correct |
32 ms |
47488 KB |
Output is correct |
33 |
Correct |
31 ms |
47488 KB |
Output is correct |
34 |
Correct |
32 ms |
47480 KB |
Output is correct |
35 |
Correct |
30 ms |
47484 KB |
Output is correct |
36 |
Correct |
30 ms |
47488 KB |
Output is correct |
37 |
Correct |
30 ms |
47488 KB |
Output is correct |
38 |
Correct |
31 ms |
47488 KB |
Output is correct |
39 |
Correct |
30 ms |
47488 KB |
Output is correct |
40 |
Correct |
30 ms |
47488 KB |
Output is correct |
41 |
Correct |
30 ms |
47608 KB |
Output is correct |
42 |
Correct |
31 ms |
47608 KB |
Output is correct |
43 |
Correct |
31 ms |
47616 KB |
Output is correct |
44 |
Correct |
31 ms |
47616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47360 KB |
Output is correct |
2 |
Correct |
28 ms |
47360 KB |
Output is correct |
3 |
Correct |
28 ms |
47360 KB |
Output is correct |
4 |
Correct |
28 ms |
47360 KB |
Output is correct |
5 |
Correct |
28 ms |
47360 KB |
Output is correct |
6 |
Correct |
28 ms |
47360 KB |
Output is correct |
7 |
Correct |
28 ms |
47224 KB |
Output is correct |
8 |
Correct |
28 ms |
47360 KB |
Output is correct |
9 |
Correct |
28 ms |
47232 KB |
Output is correct |
10 |
Correct |
28 ms |
47360 KB |
Output is correct |
11 |
Correct |
28 ms |
47360 KB |
Output is correct |
12 |
Correct |
29 ms |
47360 KB |
Output is correct |
13 |
Correct |
29 ms |
47360 KB |
Output is correct |
14 |
Correct |
29 ms |
47360 KB |
Output is correct |
15 |
Correct |
28 ms |
47360 KB |
Output is correct |
16 |
Correct |
29 ms |
47344 KB |
Output is correct |
17 |
Correct |
29 ms |
47232 KB |
Output is correct |
18 |
Correct |
28 ms |
47352 KB |
Output is correct |
19 |
Correct |
29 ms |
47360 KB |
Output is correct |
20 |
Correct |
30 ms |
47352 KB |
Output is correct |
21 |
Correct |
29 ms |
47360 KB |
Output is correct |
22 |
Correct |
29 ms |
47360 KB |
Output is correct |
23 |
Correct |
28 ms |
47232 KB |
Output is correct |
24 |
Correct |
29 ms |
47360 KB |
Output is correct |
25 |
Correct |
30 ms |
47616 KB |
Output is correct |
26 |
Correct |
31 ms |
47488 KB |
Output is correct |
27 |
Correct |
32 ms |
47488 KB |
Output is correct |
28 |
Correct |
31 ms |
47488 KB |
Output is correct |
29 |
Correct |
31 ms |
47488 KB |
Output is correct |
30 |
Correct |
32 ms |
47488 KB |
Output is correct |
31 |
Correct |
32 ms |
47480 KB |
Output is correct |
32 |
Correct |
32 ms |
47488 KB |
Output is correct |
33 |
Correct |
31 ms |
47488 KB |
Output is correct |
34 |
Correct |
32 ms |
47480 KB |
Output is correct |
35 |
Correct |
30 ms |
47484 KB |
Output is correct |
36 |
Correct |
30 ms |
47488 KB |
Output is correct |
37 |
Correct |
30 ms |
47488 KB |
Output is correct |
38 |
Correct |
31 ms |
47488 KB |
Output is correct |
39 |
Correct |
30 ms |
47488 KB |
Output is correct |
40 |
Correct |
30 ms |
47488 KB |
Output is correct |
41 |
Correct |
30 ms |
47608 KB |
Output is correct |
42 |
Correct |
31 ms |
47608 KB |
Output is correct |
43 |
Correct |
31 ms |
47616 KB |
Output is correct |
44 |
Correct |
31 ms |
47616 KB |
Output is correct |
45 |
Correct |
174 ms |
54832 KB |
Output is correct |
46 |
Correct |
176 ms |
54960 KB |
Output is correct |
47 |
Correct |
168 ms |
54704 KB |
Output is correct |
48 |
Correct |
169 ms |
55080 KB |
Output is correct |
49 |
Correct |
170 ms |
54828 KB |
Output is correct |
50 |
Correct |
174 ms |
54960 KB |
Output is correct |
51 |
Correct |
169 ms |
55216 KB |
Output is correct |
52 |
Correct |
123 ms |
50680 KB |
Output is correct |
53 |
Correct |
96 ms |
50672 KB |
Output is correct |
54 |
Correct |
108 ms |
55644 KB |
Output is correct |
55 |
Correct |
129 ms |
59816 KB |
Output is correct |
56 |
Correct |
117 ms |
55648 KB |
Output is correct |
57 |
Correct |
143 ms |
54448 KB |
Output is correct |
58 |
Correct |
122 ms |
50420 KB |
Output is correct |
59 |
Correct |
156 ms |
51764 KB |
Output is correct |
60 |
Correct |
181 ms |
53360 KB |
Output is correct |
61 |
Correct |
187 ms |
54384 KB |
Output is correct |
62 |
Correct |
166 ms |
54128 KB |
Output is correct |
63 |
Correct |
182 ms |
54320 KB |
Output is correct |
64 |
Correct |
181 ms |
54896 KB |
Output is correct |
65 |
Correct |
176 ms |
61736 KB |
Output is correct |
66 |
Correct |
192 ms |
61736 KB |
Output is correct |
67 |
Correct |
153 ms |
57312 KB |
Output is correct |
68 |
Correct |
155 ms |
56936 KB |
Output is correct |
69 |
Correct |
145 ms |
58004 KB |
Output is correct |
70 |
Correct |
141 ms |
58132 KB |
Output is correct |
71 |
Correct |
114 ms |
55928 KB |
Output is correct |
72 |
Correct |
114 ms |
55652 KB |
Output is correct |
73 |
Correct |
113 ms |
55488 KB |
Output is correct |
74 |
Correct |
111 ms |
55652 KB |
Output is correct |
75 |
Correct |
155 ms |
56240 KB |
Output is correct |
76 |
Correct |
148 ms |
57520 KB |
Output is correct |
77 |
Correct |
155 ms |
57520 KB |
Output is correct |
78 |
Correct |
171 ms |
54960 KB |
Output is correct |
79 |
Correct |
168 ms |
54832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47360 KB |
Output is correct |
2 |
Correct |
28 ms |
47360 KB |
Output is correct |
3 |
Correct |
28 ms |
47360 KB |
Output is correct |
4 |
Correct |
28 ms |
47360 KB |
Output is correct |
5 |
Correct |
28 ms |
47360 KB |
Output is correct |
6 |
Correct |
28 ms |
47360 KB |
Output is correct |
7 |
Correct |
28 ms |
47224 KB |
Output is correct |
8 |
Correct |
28 ms |
47360 KB |
Output is correct |
9 |
Correct |
28 ms |
47232 KB |
Output is correct |
10 |
Correct |
28 ms |
47360 KB |
Output is correct |
11 |
Correct |
28 ms |
47360 KB |
Output is correct |
12 |
Correct |
29 ms |
47360 KB |
Output is correct |
13 |
Correct |
29 ms |
47360 KB |
Output is correct |
14 |
Correct |
29 ms |
47360 KB |
Output is correct |
15 |
Correct |
28 ms |
47360 KB |
Output is correct |
16 |
Correct |
29 ms |
47344 KB |
Output is correct |
17 |
Correct |
29 ms |
47232 KB |
Output is correct |
18 |
Correct |
28 ms |
47352 KB |
Output is correct |
19 |
Correct |
29 ms |
47360 KB |
Output is correct |
20 |
Correct |
30 ms |
47352 KB |
Output is correct |
21 |
Correct |
29 ms |
47360 KB |
Output is correct |
22 |
Correct |
29 ms |
47360 KB |
Output is correct |
23 |
Correct |
28 ms |
47232 KB |
Output is correct |
24 |
Correct |
29 ms |
47360 KB |
Output is correct |
25 |
Correct |
30 ms |
47616 KB |
Output is correct |
26 |
Correct |
31 ms |
47488 KB |
Output is correct |
27 |
Correct |
32 ms |
47488 KB |
Output is correct |
28 |
Correct |
31 ms |
47488 KB |
Output is correct |
29 |
Correct |
31 ms |
47488 KB |
Output is correct |
30 |
Correct |
32 ms |
47488 KB |
Output is correct |
31 |
Correct |
32 ms |
47480 KB |
Output is correct |
32 |
Correct |
32 ms |
47488 KB |
Output is correct |
33 |
Correct |
31 ms |
47488 KB |
Output is correct |
34 |
Correct |
32 ms |
47480 KB |
Output is correct |
35 |
Correct |
30 ms |
47484 KB |
Output is correct |
36 |
Correct |
30 ms |
47488 KB |
Output is correct |
37 |
Correct |
30 ms |
47488 KB |
Output is correct |
38 |
Correct |
31 ms |
47488 KB |
Output is correct |
39 |
Correct |
30 ms |
47488 KB |
Output is correct |
40 |
Correct |
30 ms |
47488 KB |
Output is correct |
41 |
Correct |
30 ms |
47608 KB |
Output is correct |
42 |
Correct |
31 ms |
47608 KB |
Output is correct |
43 |
Correct |
31 ms |
47616 KB |
Output is correct |
44 |
Correct |
31 ms |
47616 KB |
Output is correct |
45 |
Correct |
174 ms |
54832 KB |
Output is correct |
46 |
Correct |
176 ms |
54960 KB |
Output is correct |
47 |
Correct |
168 ms |
54704 KB |
Output is correct |
48 |
Correct |
169 ms |
55080 KB |
Output is correct |
49 |
Correct |
170 ms |
54828 KB |
Output is correct |
50 |
Correct |
174 ms |
54960 KB |
Output is correct |
51 |
Correct |
169 ms |
55216 KB |
Output is correct |
52 |
Correct |
123 ms |
50680 KB |
Output is correct |
53 |
Correct |
96 ms |
50672 KB |
Output is correct |
54 |
Correct |
108 ms |
55644 KB |
Output is correct |
55 |
Correct |
129 ms |
59816 KB |
Output is correct |
56 |
Correct |
117 ms |
55648 KB |
Output is correct |
57 |
Correct |
143 ms |
54448 KB |
Output is correct |
58 |
Correct |
122 ms |
50420 KB |
Output is correct |
59 |
Correct |
156 ms |
51764 KB |
Output is correct |
60 |
Correct |
181 ms |
53360 KB |
Output is correct |
61 |
Correct |
187 ms |
54384 KB |
Output is correct |
62 |
Correct |
166 ms |
54128 KB |
Output is correct |
63 |
Correct |
182 ms |
54320 KB |
Output is correct |
64 |
Correct |
181 ms |
54896 KB |
Output is correct |
65 |
Correct |
176 ms |
61736 KB |
Output is correct |
66 |
Correct |
192 ms |
61736 KB |
Output is correct |
67 |
Correct |
153 ms |
57312 KB |
Output is correct |
68 |
Correct |
155 ms |
56936 KB |
Output is correct |
69 |
Correct |
145 ms |
58004 KB |
Output is correct |
70 |
Correct |
141 ms |
58132 KB |
Output is correct |
71 |
Correct |
114 ms |
55928 KB |
Output is correct |
72 |
Correct |
114 ms |
55652 KB |
Output is correct |
73 |
Correct |
113 ms |
55488 KB |
Output is correct |
74 |
Correct |
111 ms |
55652 KB |
Output is correct |
75 |
Correct |
155 ms |
56240 KB |
Output is correct |
76 |
Correct |
148 ms |
57520 KB |
Output is correct |
77 |
Correct |
155 ms |
57520 KB |
Output is correct |
78 |
Correct |
171 ms |
54960 KB |
Output is correct |
79 |
Correct |
168 ms |
54832 KB |
Output is correct |
80 |
Correct |
2120 ms |
121152 KB |
Output is correct |
81 |
Correct |
2049 ms |
121144 KB |
Output is correct |
82 |
Correct |
2124 ms |
120516 KB |
Output is correct |
83 |
Correct |
2019 ms |
120884 KB |
Output is correct |
84 |
Correct |
2081 ms |
121264 KB |
Output is correct |
85 |
Correct |
2050 ms |
121668 KB |
Output is correct |
86 |
Correct |
2087 ms |
123184 KB |
Output is correct |
87 |
Correct |
1373 ms |
79264 KB |
Output is correct |
88 |
Correct |
1026 ms |
78852 KB |
Output is correct |
89 |
Correct |
1390 ms |
129536 KB |
Output is correct |
90 |
Correct |
1710 ms |
166572 KB |
Output is correct |
91 |
Correct |
1363 ms |
129540 KB |
Output is correct |
92 |
Correct |
1759 ms |
117056 KB |
Output is correct |
93 |
Correct |
1293 ms |
79260 KB |
Output is correct |
94 |
Correct |
2013 ms |
97500 KB |
Output is correct |
95 |
Correct |
2162 ms |
115024 KB |
Output is correct |
96 |
Correct |
2071 ms |
120024 KB |
Output is correct |
97 |
Correct |
1962 ms |
104008 KB |
Output is correct |
98 |
Correct |
2154 ms |
119616 KB |
Output is correct |
99 |
Correct |
2053 ms |
123480 KB |
Output is correct |
100 |
Correct |
2595 ms |
201644 KB |
Output is correct |
101 |
Correct |
2483 ms |
188464 KB |
Output is correct |
102 |
Correct |
1963 ms |
145936 KB |
Output is correct |
103 |
Correct |
1949 ms |
148624 KB |
Output is correct |
104 |
Correct |
1868 ms |
151124 KB |
Output is correct |
105 |
Correct |
1867 ms |
150996 KB |
Output is correct |
106 |
Correct |
1556 ms |
133520 KB |
Output is correct |
107 |
Correct |
1419 ms |
133520 KB |
Output is correct |
108 |
Correct |
1334 ms |
129540 KB |
Output is correct |
109 |
Correct |
1382 ms |
129540 KB |
Output is correct |
110 |
Correct |
1896 ms |
147632 KB |
Output is correct |
111 |
Correct |
1864 ms |
148276 KB |
Output is correct |
112 |
Correct |
1867 ms |
148272 KB |
Output is correct |
113 |
Correct |
2056 ms |
120380 KB |
Output is correct |
114 |
Correct |
2049 ms |
121144 KB |
Output is correct |