#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)
// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
#define RED 0
#define BLUE 1
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
int sz;
void upd(int *st, int p, int val) {
p += sz;
st[p] = max(st[p], val);
for (; p > 1; p >>= 1) {
st[p >> 1] = max(st[p], st[p ^ 1]);
}
}
int query(int *st, int l, int r) {
int res = 0;
l += sz, r += sz;
for (; l <= r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, st[l++]);
if (!(r & 1)) res = max(res, st[r--]);
}
return res;
}
int st[2][MAXN << 2];
ii seg[MAXN];
bool exist[MAXN];
int col[MAXN];
ii st_min[MAXN << 2], st_max[MAXN << 2];
void upd_max(int idx) {
int p = seg[idx].fi + sz;
if (st_max[p].fi == seg[idx].se)
st_max[p] = mp(0, -1);
else
st_max[p] = mp(seg[idx].se, idx);
for (; p > 1; p >>= 1) {
st_max[p >> 1] = max(st_max[p], st_max[p ^ 1]);
}
}
void upd_min(int idx) {
int p = seg[idx].se + sz;
if (st_min[p].fi == seg[idx].fi)
st_min[p] = mp(INF, -1);
else
st_min[p] = mp(seg[idx].fi, idx);
for (; p > 1; p >>= 1) {
st_min[p >> 1] = min(st_min[p], st_min[p ^ 1]);
}
}
int get_max(int l, int r) {
l += sz;
r += sz;
ii res = mp(0, -1);
for (; l <= r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, st_max[l++]);
if (!(r & 1)) res = max(res, st_max[r--]);
}
return res.se;
}
int get_min(int l, int r) {
l += sz;
r += sz;
ii res = mp(INF, -1);
for (; l <= r; l >>= 1, r >>= 1) {
if (l & 1) res = min(res, st_min[l++]);
if (!(r & 1)) res = min(res, st_min[r--]);
}
return res.se;
}
void dfs(int u) {
int v;
while ((v = get_max(seg[u].fi, seg[u].se)) != -1) {
if (seg[v].se <= seg[u].se) break;
upd_max(v);
upd_min(v);
col[v] = BLUE + RED - col[u];
dfs(v);
}
while ((v = get_min(seg[u].fi, seg[u].se)) != -1) {
if (seg[v].fi >= seg[u].fi) break;
upd_min(v);
upd_max(v);
col[v] = BLUE + RED - col[u];
dfs(v);
}
}
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n;
scanf("%d", &n);
sz = 2 * n;
fill(st_min, st_min + sz * 2, mp(INF, -1));
fill(st_max, st_max + sz * 2, mp(0, -1));
for (int i = 0; i < n; i++) {
scanf("%d %d", &seg[i].fi, &seg[i].se);
seg[i].fi--;
seg[i].se--;
upd_max(i);
upd_min(i);
}
memset(col, -1, sizeof col);
int ans = 1;
for (int i = 0; i < n; i++) {
if (col[i] == -1) {
ans *= 2;
if (ans >= MOD) ans -= MOD;
col[i] = RED;
upd_max(i);
upd_min(i);
dfs(i);
}
upd(st[col[i]], seg[i].fi, seg[i].se);
}
for (int i = 0; i < n; i++) {
if (query(st[col[i]], seg[i].fi + 1, seg[i].se) > seg[i].se) {
ans = 0;
break;
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
port_facility.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &seg[i].fi, &seg[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4220 KB |
Output is correct |
2 |
Correct |
6 ms |
4328 KB |
Output is correct |
3 |
Correct |
7 ms |
4532 KB |
Output is correct |
4 |
Correct |
8 ms |
4532 KB |
Output is correct |
5 |
Correct |
6 ms |
4532 KB |
Output is correct |
6 |
Correct |
7 ms |
4532 KB |
Output is correct |
7 |
Correct |
7 ms |
4648 KB |
Output is correct |
8 |
Correct |
7 ms |
4648 KB |
Output is correct |
9 |
Correct |
6 ms |
4648 KB |
Output is correct |
10 |
Correct |
8 ms |
4648 KB |
Output is correct |
11 |
Correct |
7 ms |
4648 KB |
Output is correct |
12 |
Correct |
7 ms |
4648 KB |
Output is correct |
13 |
Correct |
8 ms |
4648 KB |
Output is correct |
14 |
Correct |
8 ms |
4648 KB |
Output is correct |
15 |
Correct |
10 ms |
4648 KB |
Output is correct |
16 |
Correct |
8 ms |
4648 KB |
Output is correct |
17 |
Correct |
7 ms |
4648 KB |
Output is correct |
18 |
Correct |
8 ms |
4648 KB |
Output is correct |
19 |
Correct |
8 ms |
4648 KB |
Output is correct |
20 |
Correct |
7 ms |
4648 KB |
Output is correct |
21 |
Correct |
7 ms |
4648 KB |
Output is correct |
22 |
Correct |
7 ms |
4648 KB |
Output is correct |
23 |
Correct |
7 ms |
4648 KB |
Output is correct |
24 |
Correct |
9 ms |
4648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4220 KB |
Output is correct |
2 |
Correct |
6 ms |
4328 KB |
Output is correct |
3 |
Correct |
7 ms |
4532 KB |
Output is correct |
4 |
Correct |
8 ms |
4532 KB |
Output is correct |
5 |
Correct |
6 ms |
4532 KB |
Output is correct |
6 |
Correct |
7 ms |
4532 KB |
Output is correct |
7 |
Correct |
7 ms |
4648 KB |
Output is correct |
8 |
Correct |
7 ms |
4648 KB |
Output is correct |
9 |
Correct |
6 ms |
4648 KB |
Output is correct |
10 |
Correct |
8 ms |
4648 KB |
Output is correct |
11 |
Correct |
7 ms |
4648 KB |
Output is correct |
12 |
Correct |
7 ms |
4648 KB |
Output is correct |
13 |
Correct |
8 ms |
4648 KB |
Output is correct |
14 |
Correct |
8 ms |
4648 KB |
Output is correct |
15 |
Correct |
10 ms |
4648 KB |
Output is correct |
16 |
Correct |
8 ms |
4648 KB |
Output is correct |
17 |
Correct |
7 ms |
4648 KB |
Output is correct |
18 |
Correct |
8 ms |
4648 KB |
Output is correct |
19 |
Correct |
8 ms |
4648 KB |
Output is correct |
20 |
Correct |
7 ms |
4648 KB |
Output is correct |
21 |
Correct |
7 ms |
4648 KB |
Output is correct |
22 |
Correct |
7 ms |
4648 KB |
Output is correct |
23 |
Correct |
7 ms |
4648 KB |
Output is correct |
24 |
Correct |
9 ms |
4648 KB |
Output is correct |
25 |
Correct |
11 ms |
4780 KB |
Output is correct |
26 |
Correct |
10 ms |
4800 KB |
Output is correct |
27 |
Correct |
11 ms |
4824 KB |
Output is correct |
28 |
Correct |
11 ms |
4840 KB |
Output is correct |
29 |
Correct |
11 ms |
4860 KB |
Output is correct |
30 |
Correct |
10 ms |
4880 KB |
Output is correct |
31 |
Correct |
9 ms |
4904 KB |
Output is correct |
32 |
Correct |
12 ms |
4920 KB |
Output is correct |
33 |
Correct |
10 ms |
4940 KB |
Output is correct |
34 |
Correct |
10 ms |
5000 KB |
Output is correct |
35 |
Correct |
11 ms |
5032 KB |
Output is correct |
36 |
Correct |
11 ms |
5032 KB |
Output is correct |
37 |
Correct |
10 ms |
5176 KB |
Output is correct |
38 |
Correct |
11 ms |
5176 KB |
Output is correct |
39 |
Correct |
11 ms |
5176 KB |
Output is correct |
40 |
Correct |
9 ms |
5176 KB |
Output is correct |
41 |
Correct |
11 ms |
5228 KB |
Output is correct |
42 |
Correct |
10 ms |
5248 KB |
Output is correct |
43 |
Correct |
10 ms |
5268 KB |
Output is correct |
44 |
Correct |
9 ms |
5288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4220 KB |
Output is correct |
2 |
Correct |
6 ms |
4328 KB |
Output is correct |
3 |
Correct |
7 ms |
4532 KB |
Output is correct |
4 |
Correct |
8 ms |
4532 KB |
Output is correct |
5 |
Correct |
6 ms |
4532 KB |
Output is correct |
6 |
Correct |
7 ms |
4532 KB |
Output is correct |
7 |
Correct |
7 ms |
4648 KB |
Output is correct |
8 |
Correct |
7 ms |
4648 KB |
Output is correct |
9 |
Correct |
6 ms |
4648 KB |
Output is correct |
10 |
Correct |
8 ms |
4648 KB |
Output is correct |
11 |
Correct |
7 ms |
4648 KB |
Output is correct |
12 |
Correct |
7 ms |
4648 KB |
Output is correct |
13 |
Correct |
8 ms |
4648 KB |
Output is correct |
14 |
Correct |
8 ms |
4648 KB |
Output is correct |
15 |
Correct |
10 ms |
4648 KB |
Output is correct |
16 |
Correct |
8 ms |
4648 KB |
Output is correct |
17 |
Correct |
7 ms |
4648 KB |
Output is correct |
18 |
Correct |
8 ms |
4648 KB |
Output is correct |
19 |
Correct |
8 ms |
4648 KB |
Output is correct |
20 |
Correct |
7 ms |
4648 KB |
Output is correct |
21 |
Correct |
7 ms |
4648 KB |
Output is correct |
22 |
Correct |
7 ms |
4648 KB |
Output is correct |
23 |
Correct |
7 ms |
4648 KB |
Output is correct |
24 |
Correct |
9 ms |
4648 KB |
Output is correct |
25 |
Correct |
11 ms |
4780 KB |
Output is correct |
26 |
Correct |
10 ms |
4800 KB |
Output is correct |
27 |
Correct |
11 ms |
4824 KB |
Output is correct |
28 |
Correct |
11 ms |
4840 KB |
Output is correct |
29 |
Correct |
11 ms |
4860 KB |
Output is correct |
30 |
Correct |
10 ms |
4880 KB |
Output is correct |
31 |
Correct |
9 ms |
4904 KB |
Output is correct |
32 |
Correct |
12 ms |
4920 KB |
Output is correct |
33 |
Correct |
10 ms |
4940 KB |
Output is correct |
34 |
Correct |
10 ms |
5000 KB |
Output is correct |
35 |
Correct |
11 ms |
5032 KB |
Output is correct |
36 |
Correct |
11 ms |
5032 KB |
Output is correct |
37 |
Correct |
10 ms |
5176 KB |
Output is correct |
38 |
Correct |
11 ms |
5176 KB |
Output is correct |
39 |
Correct |
11 ms |
5176 KB |
Output is correct |
40 |
Correct |
9 ms |
5176 KB |
Output is correct |
41 |
Correct |
11 ms |
5228 KB |
Output is correct |
42 |
Correct |
10 ms |
5248 KB |
Output is correct |
43 |
Correct |
10 ms |
5268 KB |
Output is correct |
44 |
Correct |
9 ms |
5288 KB |
Output is correct |
45 |
Correct |
265 ms |
17112 KB |
Output is correct |
46 |
Correct |
256 ms |
18988 KB |
Output is correct |
47 |
Correct |
280 ms |
19264 KB |
Output is correct |
48 |
Correct |
262 ms |
21480 KB |
Output is correct |
49 |
Correct |
286 ms |
21844 KB |
Output is correct |
50 |
Correct |
237 ms |
23860 KB |
Output is correct |
51 |
Correct |
257 ms |
25124 KB |
Output is correct |
52 |
Correct |
243 ms |
25124 KB |
Output is correct |
53 |
Correct |
299 ms |
25124 KB |
Output is correct |
54 |
Correct |
227 ms |
30052 KB |
Output is correct |
55 |
Correct |
212 ms |
30052 KB |
Output is correct |
56 |
Correct |
209 ms |
30488 KB |
Output is correct |
57 |
Correct |
220 ms |
31500 KB |
Output is correct |
58 |
Correct |
224 ms |
31500 KB |
Output is correct |
59 |
Correct |
278 ms |
34012 KB |
Output is correct |
60 |
Correct |
268 ms |
35248 KB |
Output is correct |
61 |
Correct |
310 ms |
36672 KB |
Output is correct |
62 |
Correct |
237 ms |
37760 KB |
Output is correct |
63 |
Correct |
260 ms |
39052 KB |
Output is correct |
64 |
Correct |
256 ms |
40384 KB |
Output is correct |
65 |
Correct |
347 ms |
45536 KB |
Output is correct |
66 |
Correct |
333 ms |
46884 KB |
Output is correct |
67 |
Correct |
238 ms |
46884 KB |
Output is correct |
68 |
Correct |
261 ms |
46884 KB |
Output is correct |
69 |
Correct |
246 ms |
46884 KB |
Output is correct |
70 |
Correct |
264 ms |
48124 KB |
Output is correct |
71 |
Correct |
224 ms |
51560 KB |
Output is correct |
72 |
Correct |
246 ms |
52692 KB |
Output is correct |
73 |
Correct |
234 ms |
52692 KB |
Output is correct |
74 |
Correct |
229 ms |
52692 KB |
Output is correct |
75 |
Correct |
212 ms |
52940 KB |
Output is correct |
76 |
Correct |
201 ms |
54788 KB |
Output is correct |
77 |
Correct |
193 ms |
54788 KB |
Output is correct |
78 |
Correct |
244 ms |
54788 KB |
Output is correct |
79 |
Correct |
280 ms |
54788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4220 KB |
Output is correct |
2 |
Correct |
6 ms |
4328 KB |
Output is correct |
3 |
Correct |
7 ms |
4532 KB |
Output is correct |
4 |
Correct |
8 ms |
4532 KB |
Output is correct |
5 |
Correct |
6 ms |
4532 KB |
Output is correct |
6 |
Correct |
7 ms |
4532 KB |
Output is correct |
7 |
Correct |
7 ms |
4648 KB |
Output is correct |
8 |
Correct |
7 ms |
4648 KB |
Output is correct |
9 |
Correct |
6 ms |
4648 KB |
Output is correct |
10 |
Correct |
8 ms |
4648 KB |
Output is correct |
11 |
Correct |
7 ms |
4648 KB |
Output is correct |
12 |
Correct |
7 ms |
4648 KB |
Output is correct |
13 |
Correct |
8 ms |
4648 KB |
Output is correct |
14 |
Correct |
8 ms |
4648 KB |
Output is correct |
15 |
Correct |
10 ms |
4648 KB |
Output is correct |
16 |
Correct |
8 ms |
4648 KB |
Output is correct |
17 |
Correct |
7 ms |
4648 KB |
Output is correct |
18 |
Correct |
8 ms |
4648 KB |
Output is correct |
19 |
Correct |
8 ms |
4648 KB |
Output is correct |
20 |
Correct |
7 ms |
4648 KB |
Output is correct |
21 |
Correct |
7 ms |
4648 KB |
Output is correct |
22 |
Correct |
7 ms |
4648 KB |
Output is correct |
23 |
Correct |
7 ms |
4648 KB |
Output is correct |
24 |
Correct |
9 ms |
4648 KB |
Output is correct |
25 |
Correct |
11 ms |
4780 KB |
Output is correct |
26 |
Correct |
10 ms |
4800 KB |
Output is correct |
27 |
Correct |
11 ms |
4824 KB |
Output is correct |
28 |
Correct |
11 ms |
4840 KB |
Output is correct |
29 |
Correct |
11 ms |
4860 KB |
Output is correct |
30 |
Correct |
10 ms |
4880 KB |
Output is correct |
31 |
Correct |
9 ms |
4904 KB |
Output is correct |
32 |
Correct |
12 ms |
4920 KB |
Output is correct |
33 |
Correct |
10 ms |
4940 KB |
Output is correct |
34 |
Correct |
10 ms |
5000 KB |
Output is correct |
35 |
Correct |
11 ms |
5032 KB |
Output is correct |
36 |
Correct |
11 ms |
5032 KB |
Output is correct |
37 |
Correct |
10 ms |
5176 KB |
Output is correct |
38 |
Correct |
11 ms |
5176 KB |
Output is correct |
39 |
Correct |
11 ms |
5176 KB |
Output is correct |
40 |
Correct |
9 ms |
5176 KB |
Output is correct |
41 |
Correct |
11 ms |
5228 KB |
Output is correct |
42 |
Correct |
10 ms |
5248 KB |
Output is correct |
43 |
Correct |
10 ms |
5268 KB |
Output is correct |
44 |
Correct |
9 ms |
5288 KB |
Output is correct |
45 |
Correct |
265 ms |
17112 KB |
Output is correct |
46 |
Correct |
256 ms |
18988 KB |
Output is correct |
47 |
Correct |
280 ms |
19264 KB |
Output is correct |
48 |
Correct |
262 ms |
21480 KB |
Output is correct |
49 |
Correct |
286 ms |
21844 KB |
Output is correct |
50 |
Correct |
237 ms |
23860 KB |
Output is correct |
51 |
Correct |
257 ms |
25124 KB |
Output is correct |
52 |
Correct |
243 ms |
25124 KB |
Output is correct |
53 |
Correct |
299 ms |
25124 KB |
Output is correct |
54 |
Correct |
227 ms |
30052 KB |
Output is correct |
55 |
Correct |
212 ms |
30052 KB |
Output is correct |
56 |
Correct |
209 ms |
30488 KB |
Output is correct |
57 |
Correct |
220 ms |
31500 KB |
Output is correct |
58 |
Correct |
224 ms |
31500 KB |
Output is correct |
59 |
Correct |
278 ms |
34012 KB |
Output is correct |
60 |
Correct |
268 ms |
35248 KB |
Output is correct |
61 |
Correct |
310 ms |
36672 KB |
Output is correct |
62 |
Correct |
237 ms |
37760 KB |
Output is correct |
63 |
Correct |
260 ms |
39052 KB |
Output is correct |
64 |
Correct |
256 ms |
40384 KB |
Output is correct |
65 |
Correct |
347 ms |
45536 KB |
Output is correct |
66 |
Correct |
333 ms |
46884 KB |
Output is correct |
67 |
Correct |
238 ms |
46884 KB |
Output is correct |
68 |
Correct |
261 ms |
46884 KB |
Output is correct |
69 |
Correct |
246 ms |
46884 KB |
Output is correct |
70 |
Correct |
264 ms |
48124 KB |
Output is correct |
71 |
Correct |
224 ms |
51560 KB |
Output is correct |
72 |
Correct |
246 ms |
52692 KB |
Output is correct |
73 |
Correct |
234 ms |
52692 KB |
Output is correct |
74 |
Correct |
229 ms |
52692 KB |
Output is correct |
75 |
Correct |
212 ms |
52940 KB |
Output is correct |
76 |
Correct |
201 ms |
54788 KB |
Output is correct |
77 |
Correct |
193 ms |
54788 KB |
Output is correct |
78 |
Correct |
244 ms |
54788 KB |
Output is correct |
79 |
Correct |
280 ms |
54788 KB |
Output is correct |
80 |
Correct |
3598 ms |
159156 KB |
Output is correct |
81 |
Correct |
3263 ms |
172972 KB |
Output is correct |
82 |
Correct |
2550 ms |
185904 KB |
Output is correct |
83 |
Correct |
2638 ms |
202324 KB |
Output is correct |
84 |
Correct |
2718 ms |
217288 KB |
Output is correct |
85 |
Correct |
2460 ms |
229732 KB |
Output is correct |
86 |
Correct |
2386 ms |
245856 KB |
Output is correct |
87 |
Correct |
2459 ms |
245856 KB |
Output is correct |
88 |
Correct |
3122 ms |
249332 KB |
Output is correct |
89 |
Correct |
2262 ms |
308276 KB |
Output is correct |
90 |
Correct |
2335 ms |
308276 KB |
Output is correct |
91 |
Correct |
2455 ms |
308276 KB |
Output is correct |
92 |
Correct |
2413 ms |
308276 KB |
Output is correct |
93 |
Correct |
2717 ms |
308276 KB |
Output is correct |
94 |
Correct |
3589 ms |
337028 KB |
Output is correct |
95 |
Correct |
3426 ms |
351640 KB |
Output is correct |
96 |
Correct |
3149 ms |
366172 KB |
Output is correct |
97 |
Correct |
3317 ms |
380696 KB |
Output is correct |
98 |
Correct |
3168 ms |
395212 KB |
Output is correct |
99 |
Correct |
3056 ms |
409712 KB |
Output is correct |
100 |
Correct |
4508 ms |
462200 KB |
Output is correct |
101 |
Correct |
4549 ms |
475092 KB |
Output is correct |
102 |
Correct |
3099 ms |
475092 KB |
Output is correct |
103 |
Correct |
2954 ms |
475092 KB |
Output is correct |
104 |
Correct |
2607 ms |
478888 KB |
Output is correct |
105 |
Correct |
2463 ms |
491132 KB |
Output is correct |
106 |
Correct |
2728 ms |
521536 KB |
Output is correct |
107 |
Correct |
2923 ms |
530952 KB |
Output is correct |
108 |
Correct |
2850 ms |
530952 KB |
Output is correct |
109 |
Correct |
2803 ms |
539692 KB |
Output is correct |
110 |
Correct |
2648 ms |
573668 KB |
Output is correct |
111 |
Correct |
2602 ms |
589196 KB |
Output is correct |
112 |
Correct |
2448 ms |
603752 KB |
Output is correct |
113 |
Correct |
3106 ms |
603752 KB |
Output is correct |
114 |
Correct |
3247 ms |
603752 KB |
Output is correct |