#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
const int mod = 1e9 + 7; int mp(int x, int a) {
if (a == 0) return 1; int ret = mp(x, a >> 1); if (a & 1) return 1ll * ret * ret % mod * x % mod;
return 1ll * ret * ret % mod;
}
int N;
pii P[1000005];
int idx[2000005];
const int SIZE = 1 << 21;
struct ST {
vector<pii> A;
ST() { A.resize(2 * SIZE); }
void update(int x, int v) {
x += SIZE;
A[x] = {v, x - SIZE};
for (x >>= 1; x; x >>= 1) A[x] = max(A[x << 1], A[x << 1 | 1]);
}
pii query(int s, int e) {
pii ret = {0, 0};
for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
if ( s & 1) ret = max(ret, A[s++]);
if (~e & 1) ret = max(ret, A[e--]);
}
return ret;
}
} seg1, seg2;
bool vis[1000005], C[1000005];
vector<int> A, B;
void dfs(int x) {
if (C[x]) A.push_back(x);
else B.push_back(x);
vis[x] = 1;
vector<int> v;
while (1) {
auto t = seg1.query(P[x].ff, P[x].ss);
if (2 * N + 1 - t.ff > P[x].ff) break;
seg1.update(t.ss, 0);
seg2.update(2 * N + 1 - t.ff, 0);
v.push_back(idx[2 * N + 1 - t.ff]);
}
while (1) {
auto t = seg2.query(P[x].ff, P[x].ss);
if (t.ff < P[x].ss) break;
seg1.update(t.ff, 0);
seg2.update(t.ss, 0);
v.push_back(idx[t.ss]);
}
for (auto i : v) C[i] = C[x] ^ 1, dfs(i);
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
int a, b; cin >> a >> b;
P[i] = {a, b};
}
sort(P, P + N);
for (int i = 0; i < N; ++i) seg1.update(P[i].ss, 2 * N + 1 - P[i].ff), seg2.update(P[i].ff, P[i].ss), idx[P[i].ff] = i;
int cnt = 0;
for (int i = N - 1; i >= 0; --i) {
if (vis[i]) continue;
cnt++;
seg1.update(P[i].ss, 0);
seg2.update(P[i].ff, 0);
dfs(i);
}
priority_queue<int, vector<int>, greater<int> > pq;
sort(A.begin(), A.end());
sort(B.begin(), B.end());
for (auto i : A) {
while (pq.size() && pq.top() < P[i].ff) pq.pop();
if (pq.size() && pq.top() < P[i].ss) return !printf("0");
pq.push(P[i].ss);
}
while (pq.size()) pq.pop();
for (auto i : B) {
while (pq.size() && pq.top() < P[i].ff) pq.pop();
if (pq.size() && pq.top() < P[i].ss) return !printf("0");
pq.push(P[i].ss);
}
cout << mp(2, cnt);
return 0;
}
Compilation message
port_facility.cpp: In function 'int mp(int, int)':
port_facility.cpp:7:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (a == 0) return 1; int ret = mp(x, a >> 1); if (a & 1) return 1ll * ret * ret % mod * x % mod;
^~
port_facility.cpp:7:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if (a == 0) return 1; int ret = mp(x, a >> 1); if (a & 1) return 1ll * ret * ret % mod * x % mod;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
66040 KB |
Output is correct |
2 |
Correct |
58 ms |
66044 KB |
Output is correct |
3 |
Correct |
58 ms |
66040 KB |
Output is correct |
4 |
Correct |
58 ms |
66040 KB |
Output is correct |
5 |
Correct |
58 ms |
66040 KB |
Output is correct |
6 |
Correct |
58 ms |
66040 KB |
Output is correct |
7 |
Correct |
58 ms |
66052 KB |
Output is correct |
8 |
Correct |
58 ms |
66040 KB |
Output is correct |
9 |
Correct |
58 ms |
66040 KB |
Output is correct |
10 |
Correct |
58 ms |
66040 KB |
Output is correct |
11 |
Correct |
58 ms |
66040 KB |
Output is correct |
12 |
Correct |
58 ms |
66040 KB |
Output is correct |
13 |
Correct |
58 ms |
66040 KB |
Output is correct |
14 |
Correct |
58 ms |
66040 KB |
Output is correct |
15 |
Correct |
58 ms |
66032 KB |
Output is correct |
16 |
Correct |
59 ms |
66040 KB |
Output is correct |
17 |
Correct |
58 ms |
66040 KB |
Output is correct |
18 |
Correct |
59 ms |
66040 KB |
Output is correct |
19 |
Correct |
58 ms |
66040 KB |
Output is correct |
20 |
Correct |
58 ms |
66084 KB |
Output is correct |
21 |
Correct |
58 ms |
66068 KB |
Output is correct |
22 |
Correct |
58 ms |
66040 KB |
Output is correct |
23 |
Correct |
58 ms |
65992 KB |
Output is correct |
24 |
Correct |
58 ms |
66040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
66040 KB |
Output is correct |
2 |
Correct |
58 ms |
66044 KB |
Output is correct |
3 |
Correct |
58 ms |
66040 KB |
Output is correct |
4 |
Correct |
58 ms |
66040 KB |
Output is correct |
5 |
Correct |
58 ms |
66040 KB |
Output is correct |
6 |
Correct |
58 ms |
66040 KB |
Output is correct |
7 |
Correct |
58 ms |
66052 KB |
Output is correct |
8 |
Correct |
58 ms |
66040 KB |
Output is correct |
9 |
Correct |
58 ms |
66040 KB |
Output is correct |
10 |
Correct |
58 ms |
66040 KB |
Output is correct |
11 |
Correct |
58 ms |
66040 KB |
Output is correct |
12 |
Correct |
58 ms |
66040 KB |
Output is correct |
13 |
Correct |
58 ms |
66040 KB |
Output is correct |
14 |
Correct |
58 ms |
66040 KB |
Output is correct |
15 |
Correct |
58 ms |
66032 KB |
Output is correct |
16 |
Correct |
59 ms |
66040 KB |
Output is correct |
17 |
Correct |
58 ms |
66040 KB |
Output is correct |
18 |
Correct |
59 ms |
66040 KB |
Output is correct |
19 |
Correct |
58 ms |
66040 KB |
Output is correct |
20 |
Correct |
58 ms |
66084 KB |
Output is correct |
21 |
Correct |
58 ms |
66068 KB |
Output is correct |
22 |
Correct |
58 ms |
66040 KB |
Output is correct |
23 |
Correct |
58 ms |
65992 KB |
Output is correct |
24 |
Correct |
58 ms |
66040 KB |
Output is correct |
25 |
Correct |
62 ms |
66096 KB |
Output is correct |
26 |
Correct |
62 ms |
66040 KB |
Output is correct |
27 |
Correct |
63 ms |
66040 KB |
Output is correct |
28 |
Correct |
62 ms |
66040 KB |
Output is correct |
29 |
Correct |
62 ms |
66036 KB |
Output is correct |
30 |
Correct |
62 ms |
66168 KB |
Output is correct |
31 |
Correct |
62 ms |
66040 KB |
Output is correct |
32 |
Correct |
62 ms |
66168 KB |
Output is correct |
33 |
Correct |
62 ms |
66084 KB |
Output is correct |
34 |
Correct |
62 ms |
66168 KB |
Output is correct |
35 |
Correct |
61 ms |
66044 KB |
Output is correct |
36 |
Correct |
61 ms |
66012 KB |
Output is correct |
37 |
Correct |
61 ms |
66060 KB |
Output is correct |
38 |
Correct |
61 ms |
66168 KB |
Output is correct |
39 |
Correct |
60 ms |
66040 KB |
Output is correct |
40 |
Correct |
61 ms |
66168 KB |
Output is correct |
41 |
Correct |
62 ms |
66040 KB |
Output is correct |
42 |
Correct |
61 ms |
66040 KB |
Output is correct |
43 |
Correct |
61 ms |
66540 KB |
Output is correct |
44 |
Correct |
62 ms |
66428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
66040 KB |
Output is correct |
2 |
Correct |
58 ms |
66044 KB |
Output is correct |
3 |
Correct |
58 ms |
66040 KB |
Output is correct |
4 |
Correct |
58 ms |
66040 KB |
Output is correct |
5 |
Correct |
58 ms |
66040 KB |
Output is correct |
6 |
Correct |
58 ms |
66040 KB |
Output is correct |
7 |
Correct |
58 ms |
66052 KB |
Output is correct |
8 |
Correct |
58 ms |
66040 KB |
Output is correct |
9 |
Correct |
58 ms |
66040 KB |
Output is correct |
10 |
Correct |
58 ms |
66040 KB |
Output is correct |
11 |
Correct |
58 ms |
66040 KB |
Output is correct |
12 |
Correct |
58 ms |
66040 KB |
Output is correct |
13 |
Correct |
58 ms |
66040 KB |
Output is correct |
14 |
Correct |
58 ms |
66040 KB |
Output is correct |
15 |
Correct |
58 ms |
66032 KB |
Output is correct |
16 |
Correct |
59 ms |
66040 KB |
Output is correct |
17 |
Correct |
58 ms |
66040 KB |
Output is correct |
18 |
Correct |
59 ms |
66040 KB |
Output is correct |
19 |
Correct |
58 ms |
66040 KB |
Output is correct |
20 |
Correct |
58 ms |
66084 KB |
Output is correct |
21 |
Correct |
58 ms |
66068 KB |
Output is correct |
22 |
Correct |
58 ms |
66040 KB |
Output is correct |
23 |
Correct |
58 ms |
65992 KB |
Output is correct |
24 |
Correct |
58 ms |
66040 KB |
Output is correct |
25 |
Correct |
62 ms |
66096 KB |
Output is correct |
26 |
Correct |
62 ms |
66040 KB |
Output is correct |
27 |
Correct |
63 ms |
66040 KB |
Output is correct |
28 |
Correct |
62 ms |
66040 KB |
Output is correct |
29 |
Correct |
62 ms |
66036 KB |
Output is correct |
30 |
Correct |
62 ms |
66168 KB |
Output is correct |
31 |
Correct |
62 ms |
66040 KB |
Output is correct |
32 |
Correct |
62 ms |
66168 KB |
Output is correct |
33 |
Correct |
62 ms |
66084 KB |
Output is correct |
34 |
Correct |
62 ms |
66168 KB |
Output is correct |
35 |
Correct |
61 ms |
66044 KB |
Output is correct |
36 |
Correct |
61 ms |
66012 KB |
Output is correct |
37 |
Correct |
61 ms |
66060 KB |
Output is correct |
38 |
Correct |
61 ms |
66168 KB |
Output is correct |
39 |
Correct |
60 ms |
66040 KB |
Output is correct |
40 |
Correct |
61 ms |
66168 KB |
Output is correct |
41 |
Correct |
62 ms |
66040 KB |
Output is correct |
42 |
Correct |
61 ms |
66040 KB |
Output is correct |
43 |
Correct |
61 ms |
66540 KB |
Output is correct |
44 |
Correct |
62 ms |
66428 KB |
Output is correct |
45 |
Correct |
257 ms |
69872 KB |
Output is correct |
46 |
Correct |
256 ms |
69904 KB |
Output is correct |
47 |
Correct |
259 ms |
69764 KB |
Output is correct |
48 |
Correct |
256 ms |
69748 KB |
Output is correct |
49 |
Correct |
258 ms |
69900 KB |
Output is correct |
50 |
Correct |
248 ms |
69988 KB |
Output is correct |
51 |
Correct |
249 ms |
69800 KB |
Output is correct |
52 |
Correct |
226 ms |
69620 KB |
Output is correct |
53 |
Correct |
232 ms |
69748 KB |
Output is correct |
54 |
Correct |
240 ms |
69744 KB |
Output is correct |
55 |
Correct |
251 ms |
69652 KB |
Output is correct |
56 |
Correct |
248 ms |
69648 KB |
Output is correct |
57 |
Correct |
216 ms |
69620 KB |
Output is correct |
58 |
Correct |
216 ms |
69592 KB |
Output is correct |
59 |
Correct |
232 ms |
69820 KB |
Output is correct |
60 |
Correct |
248 ms |
69748 KB |
Output is correct |
61 |
Correct |
281 ms |
69696 KB |
Output is correct |
62 |
Correct |
231 ms |
69832 KB |
Output is correct |
63 |
Correct |
255 ms |
69708 KB |
Output is correct |
64 |
Correct |
248 ms |
69624 KB |
Output is correct |
65 |
Correct |
277 ms |
69672 KB |
Output is correct |
66 |
Correct |
286 ms |
69748 KB |
Output is correct |
67 |
Correct |
265 ms |
69740 KB |
Output is correct |
68 |
Correct |
258 ms |
69860 KB |
Output is correct |
69 |
Correct |
248 ms |
70000 KB |
Output is correct |
70 |
Correct |
247 ms |
70000 KB |
Output is correct |
71 |
Correct |
253 ms |
69584 KB |
Output is correct |
72 |
Correct |
247 ms |
69592 KB |
Output is correct |
73 |
Correct |
245 ms |
69788 KB |
Output is correct |
74 |
Correct |
246 ms |
69924 KB |
Output is correct |
75 |
Correct |
240 ms |
85104 KB |
Output is correct |
76 |
Correct |
244 ms |
85104 KB |
Output is correct |
77 |
Correct |
236 ms |
85208 KB |
Output is correct |
78 |
Correct |
256 ms |
69728 KB |
Output is correct |
79 |
Correct |
256 ms |
69744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
66040 KB |
Output is correct |
2 |
Correct |
58 ms |
66044 KB |
Output is correct |
3 |
Correct |
58 ms |
66040 KB |
Output is correct |
4 |
Correct |
58 ms |
66040 KB |
Output is correct |
5 |
Correct |
58 ms |
66040 KB |
Output is correct |
6 |
Correct |
58 ms |
66040 KB |
Output is correct |
7 |
Correct |
58 ms |
66052 KB |
Output is correct |
8 |
Correct |
58 ms |
66040 KB |
Output is correct |
9 |
Correct |
58 ms |
66040 KB |
Output is correct |
10 |
Correct |
58 ms |
66040 KB |
Output is correct |
11 |
Correct |
58 ms |
66040 KB |
Output is correct |
12 |
Correct |
58 ms |
66040 KB |
Output is correct |
13 |
Correct |
58 ms |
66040 KB |
Output is correct |
14 |
Correct |
58 ms |
66040 KB |
Output is correct |
15 |
Correct |
58 ms |
66032 KB |
Output is correct |
16 |
Correct |
59 ms |
66040 KB |
Output is correct |
17 |
Correct |
58 ms |
66040 KB |
Output is correct |
18 |
Correct |
59 ms |
66040 KB |
Output is correct |
19 |
Correct |
58 ms |
66040 KB |
Output is correct |
20 |
Correct |
58 ms |
66084 KB |
Output is correct |
21 |
Correct |
58 ms |
66068 KB |
Output is correct |
22 |
Correct |
58 ms |
66040 KB |
Output is correct |
23 |
Correct |
58 ms |
65992 KB |
Output is correct |
24 |
Correct |
58 ms |
66040 KB |
Output is correct |
25 |
Correct |
62 ms |
66096 KB |
Output is correct |
26 |
Correct |
62 ms |
66040 KB |
Output is correct |
27 |
Correct |
63 ms |
66040 KB |
Output is correct |
28 |
Correct |
62 ms |
66040 KB |
Output is correct |
29 |
Correct |
62 ms |
66036 KB |
Output is correct |
30 |
Correct |
62 ms |
66168 KB |
Output is correct |
31 |
Correct |
62 ms |
66040 KB |
Output is correct |
32 |
Correct |
62 ms |
66168 KB |
Output is correct |
33 |
Correct |
62 ms |
66084 KB |
Output is correct |
34 |
Correct |
62 ms |
66168 KB |
Output is correct |
35 |
Correct |
61 ms |
66044 KB |
Output is correct |
36 |
Correct |
61 ms |
66012 KB |
Output is correct |
37 |
Correct |
61 ms |
66060 KB |
Output is correct |
38 |
Correct |
61 ms |
66168 KB |
Output is correct |
39 |
Correct |
60 ms |
66040 KB |
Output is correct |
40 |
Correct |
61 ms |
66168 KB |
Output is correct |
41 |
Correct |
62 ms |
66040 KB |
Output is correct |
42 |
Correct |
61 ms |
66040 KB |
Output is correct |
43 |
Correct |
61 ms |
66540 KB |
Output is correct |
44 |
Correct |
62 ms |
66428 KB |
Output is correct |
45 |
Correct |
257 ms |
69872 KB |
Output is correct |
46 |
Correct |
256 ms |
69904 KB |
Output is correct |
47 |
Correct |
259 ms |
69764 KB |
Output is correct |
48 |
Correct |
256 ms |
69748 KB |
Output is correct |
49 |
Correct |
258 ms |
69900 KB |
Output is correct |
50 |
Correct |
248 ms |
69988 KB |
Output is correct |
51 |
Correct |
249 ms |
69800 KB |
Output is correct |
52 |
Correct |
226 ms |
69620 KB |
Output is correct |
53 |
Correct |
232 ms |
69748 KB |
Output is correct |
54 |
Correct |
240 ms |
69744 KB |
Output is correct |
55 |
Correct |
251 ms |
69652 KB |
Output is correct |
56 |
Correct |
248 ms |
69648 KB |
Output is correct |
57 |
Correct |
216 ms |
69620 KB |
Output is correct |
58 |
Correct |
216 ms |
69592 KB |
Output is correct |
59 |
Correct |
232 ms |
69820 KB |
Output is correct |
60 |
Correct |
248 ms |
69748 KB |
Output is correct |
61 |
Correct |
281 ms |
69696 KB |
Output is correct |
62 |
Correct |
231 ms |
69832 KB |
Output is correct |
63 |
Correct |
255 ms |
69708 KB |
Output is correct |
64 |
Correct |
248 ms |
69624 KB |
Output is correct |
65 |
Correct |
277 ms |
69672 KB |
Output is correct |
66 |
Correct |
286 ms |
69748 KB |
Output is correct |
67 |
Correct |
265 ms |
69740 KB |
Output is correct |
68 |
Correct |
258 ms |
69860 KB |
Output is correct |
69 |
Correct |
248 ms |
70000 KB |
Output is correct |
70 |
Correct |
247 ms |
70000 KB |
Output is correct |
71 |
Correct |
253 ms |
69584 KB |
Output is correct |
72 |
Correct |
247 ms |
69592 KB |
Output is correct |
73 |
Correct |
245 ms |
69788 KB |
Output is correct |
74 |
Correct |
246 ms |
69924 KB |
Output is correct |
75 |
Correct |
240 ms |
85104 KB |
Output is correct |
76 |
Correct |
244 ms |
85104 KB |
Output is correct |
77 |
Correct |
236 ms |
85208 KB |
Output is correct |
78 |
Correct |
256 ms |
69728 KB |
Output is correct |
79 |
Correct |
256 ms |
69744 KB |
Output is correct |
80 |
Correct |
2229 ms |
104576 KB |
Output is correct |
81 |
Correct |
2209 ms |
104452 KB |
Output is correct |
82 |
Correct |
2222 ms |
104224 KB |
Output is correct |
83 |
Correct |
2228 ms |
104468 KB |
Output is correct |
84 |
Correct |
2243 ms |
104688 KB |
Output is correct |
85 |
Correct |
2114 ms |
105224 KB |
Output is correct |
86 |
Correct |
2112 ms |
105108 KB |
Output is correct |
87 |
Correct |
1764 ms |
101472 KB |
Output is correct |
88 |
Correct |
1860 ms |
103520 KB |
Output is correct |
89 |
Correct |
2032 ms |
103560 KB |
Output is correct |
90 |
Correct |
2028 ms |
102368 KB |
Output is correct |
91 |
Correct |
2025 ms |
102324 KB |
Output is correct |
92 |
Correct |
1795 ms |
102360 KB |
Output is correct |
93 |
Correct |
1768 ms |
101416 KB |
Output is correct |
94 |
Correct |
2069 ms |
105744 KB |
Output is correct |
95 |
Correct |
2190 ms |
104116 KB |
Output is correct |
96 |
Correct |
2229 ms |
104200 KB |
Output is correct |
97 |
Correct |
1982 ms |
103632 KB |
Output is correct |
98 |
Correct |
2093 ms |
104924 KB |
Output is correct |
99 |
Correct |
2119 ms |
103584 KB |
Output is correct |
100 |
Correct |
2764 ms |
106528 KB |
Output is correct |
101 |
Correct |
2757 ms |
106568 KB |
Output is correct |
102 |
Correct |
2150 ms |
104280 KB |
Output is correct |
103 |
Correct |
2177 ms |
104348 KB |
Output is correct |
104 |
Correct |
2178 ms |
106416 KB |
Output is correct |
105 |
Correct |
2119 ms |
106468 KB |
Output is correct |
106 |
Correct |
2100 ms |
102448 KB |
Output is correct |
107 |
Correct |
2093 ms |
102416 KB |
Output is correct |
108 |
Correct |
2090 ms |
105160 KB |
Output is correct |
109 |
Correct |
2092 ms |
105080 KB |
Output is correct |
110 |
Correct |
1995 ms |
258860 KB |
Output is correct |
111 |
Correct |
1972 ms |
258780 KB |
Output is correct |
112 |
Correct |
1975 ms |
258776 KB |
Output is correct |
113 |
Correct |
2244 ms |
104488 KB |
Output is correct |
114 |
Correct |
2203 ms |
104748 KB |
Output is correct |