#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)
using namespace std;
typedef pair <int, int> II;
typedef long long LL;
const int N = 2 * (1e6 + 10);
const int LG = 25;
const int INF = 0x3f3f3f3f;
const int BASE = 1e9 + 7;
int n;
int a[N], L[N], R[N], pos[N];
struct DSU {
int p[N];
void Init() {
memset(p, -1, sizeof p);
}
int Root(int u) {
return p[u] < 0 ? u : p[u] = Root(p[u]);
}
void Union(int u, int v) {
u = Root(u); v = Root(v);
if (u == v) return;
if (p[u] > p[v]) swap(u, v);
p[u] += p[v];
p[v] = u;
}
} DSU;
set <int> S;
int Find(int v) {
set <int> :: iterator it = S.lower_bound(v);
if (it == S.begin()) return -1;
else return *(--it);
}
struct RMQ {
int lg[N];
int spT[2][N][LG];
void Init() {
FOR(i, 1, 2 * n) {
spT[0][i][0] = (a[i] > i ? a[i] : 0);
spT[1][i][0] = ((a[i] != 0 && a[i] < i) ? a[i] : INF);
}
for (int j = 1; 1 << j <= 2 * n; ++j)
for (int i = 1; i + (1 << j) - 1 <= 2 * n; ++i) {
spT[0][i][j] = max(spT[0][i][j - 1], spT[0][i + (1 << (j - 1))][j - 1]);
spT[1][i][j] = min(spT[1][i][j - 1], spT[1][i + (1 << (j - 1))][j - 1]);
}
for (int i = 0; 1 << i <= 2 * n; ++i) lg[1 << i] = i;
FOR(i, 1, 2 * n) if (!lg[i]) lg[i] = lg[i - 1];
}
int Query(int t, int l, int r) {
int k = lg[r - l + 1];
if (t == 0)return max(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
else return min(spT[t][l][k], spT[t][r - (1 << k) + 1][k]);
}
} RMQ;
bool Intersect(int x, int y) {
int l1 = L[x], r1 = R[x];
int l2 = L[y], r2 = R[y];
if (l2 > r1 || r2 < l1) return false;
if (l1 < l2 && r2 < r1) return false;
if (l2 < l1 && r1 < r2) return false;
return true;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d", &n);
FOR(i, 1, n) {
int l, r; scanf("%d%d", &l, &r);
L[i] = l; R[i] = r;
a[l] = r;
a[r] = l;
pos[l] = i;
pos[r] = i;
}
RMQ.Init();
DSU.Init();
FOR(timer, 1, 2 * n) {
if (a[timer] == 0) continue;
if (a[timer] > timer) {
int l2 = timer, r2 = a[timer];
int r1 = Find(r2);
if (r1 != -1) {
if (l2 < r1 && RMQ.Query(0, l2, r1) > r2) {
puts("0");
return 0;
}
}
S.insert(a[timer]);
} else {
S.erase(timer);
}
}
int fre = 0;
FOR(timer, 1, 2 * n) {
if (a[timer] > timer) {
int l = timer, r = a[timer];
int lMin = RMQ.Query(1, l, r), rMax = RMQ.Query(0, l, r);
if (lMin < l) DSU.Union(pos[timer], pos[lMin]);
if (rMax > r) DSU.Union(pos[timer], pos[rMax]);
}
}
int cmp = 0;
FOR(i, 1, n) if (DSU.p[i] < 0) ++cmp;
int ans = 1;
FOR(i, 1, cmp) ans = (LL)ans * 2 % BASE;
cout << ans;
return 0;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:113:9: warning: unused variable 'fre' [-Wunused-variable]
int fre = 0;
^
port_facility.cpp:86:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
port_facility.cpp:88:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int l, r; scanf("%d%d", &l, &r);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8184 KB |
Output is correct |
2 |
Correct |
7 ms |
8288 KB |
Output is correct |
3 |
Correct |
7 ms |
8400 KB |
Output is correct |
4 |
Correct |
7 ms |
8400 KB |
Output is correct |
5 |
Correct |
8 ms |
8416 KB |
Output is correct |
6 |
Correct |
7 ms |
8420 KB |
Output is correct |
7 |
Correct |
7 ms |
8424 KB |
Output is correct |
8 |
Correct |
7 ms |
8556 KB |
Output is correct |
9 |
Correct |
7 ms |
8556 KB |
Output is correct |
10 |
Correct |
8 ms |
8580 KB |
Output is correct |
11 |
Correct |
7 ms |
8580 KB |
Output is correct |
12 |
Correct |
7 ms |
8580 KB |
Output is correct |
13 |
Correct |
7 ms |
8600 KB |
Output is correct |
14 |
Correct |
7 ms |
8652 KB |
Output is correct |
15 |
Correct |
8 ms |
8652 KB |
Output is correct |
16 |
Correct |
9 ms |
8652 KB |
Output is correct |
17 |
Correct |
8 ms |
8652 KB |
Output is correct |
18 |
Correct |
8 ms |
8652 KB |
Output is correct |
19 |
Correct |
8 ms |
8652 KB |
Output is correct |
20 |
Correct |
9 ms |
8652 KB |
Output is correct |
21 |
Correct |
8 ms |
8652 KB |
Output is correct |
22 |
Correct |
7 ms |
8652 KB |
Output is correct |
23 |
Correct |
7 ms |
8652 KB |
Output is correct |
24 |
Correct |
7 ms |
8652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8184 KB |
Output is correct |
2 |
Correct |
7 ms |
8288 KB |
Output is correct |
3 |
Correct |
7 ms |
8400 KB |
Output is correct |
4 |
Correct |
7 ms |
8400 KB |
Output is correct |
5 |
Correct |
8 ms |
8416 KB |
Output is correct |
6 |
Correct |
7 ms |
8420 KB |
Output is correct |
7 |
Correct |
7 ms |
8424 KB |
Output is correct |
8 |
Correct |
7 ms |
8556 KB |
Output is correct |
9 |
Correct |
7 ms |
8556 KB |
Output is correct |
10 |
Correct |
8 ms |
8580 KB |
Output is correct |
11 |
Correct |
7 ms |
8580 KB |
Output is correct |
12 |
Correct |
7 ms |
8580 KB |
Output is correct |
13 |
Correct |
7 ms |
8600 KB |
Output is correct |
14 |
Correct |
7 ms |
8652 KB |
Output is correct |
15 |
Correct |
8 ms |
8652 KB |
Output is correct |
16 |
Correct |
9 ms |
8652 KB |
Output is correct |
17 |
Correct |
8 ms |
8652 KB |
Output is correct |
18 |
Correct |
8 ms |
8652 KB |
Output is correct |
19 |
Correct |
8 ms |
8652 KB |
Output is correct |
20 |
Correct |
9 ms |
8652 KB |
Output is correct |
21 |
Correct |
8 ms |
8652 KB |
Output is correct |
22 |
Correct |
7 ms |
8652 KB |
Output is correct |
23 |
Correct |
7 ms |
8652 KB |
Output is correct |
24 |
Correct |
7 ms |
8652 KB |
Output is correct |
25 |
Correct |
10 ms |
9516 KB |
Output is correct |
26 |
Correct |
10 ms |
9536 KB |
Output is correct |
27 |
Correct |
10 ms |
9572 KB |
Output is correct |
28 |
Correct |
10 ms |
9636 KB |
Output is correct |
29 |
Correct |
10 ms |
9696 KB |
Output is correct |
30 |
Correct |
12 ms |
9696 KB |
Output is correct |
31 |
Correct |
9 ms |
9696 KB |
Output is correct |
32 |
Correct |
11 ms |
9736 KB |
Output is correct |
33 |
Correct |
9 ms |
9804 KB |
Output is correct |
34 |
Correct |
8 ms |
9804 KB |
Output is correct |
35 |
Correct |
9 ms |
9804 KB |
Output is correct |
36 |
Correct |
9 ms |
9804 KB |
Output is correct |
37 |
Correct |
9 ms |
9804 KB |
Output is correct |
38 |
Correct |
8 ms |
9808 KB |
Output is correct |
39 |
Correct |
8 ms |
9832 KB |
Output is correct |
40 |
Correct |
9 ms |
9832 KB |
Output is correct |
41 |
Correct |
9 ms |
9868 KB |
Output is correct |
42 |
Correct |
10 ms |
9888 KB |
Output is correct |
43 |
Incorrect |
10 ms |
9908 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8184 KB |
Output is correct |
2 |
Correct |
7 ms |
8288 KB |
Output is correct |
3 |
Correct |
7 ms |
8400 KB |
Output is correct |
4 |
Correct |
7 ms |
8400 KB |
Output is correct |
5 |
Correct |
8 ms |
8416 KB |
Output is correct |
6 |
Correct |
7 ms |
8420 KB |
Output is correct |
7 |
Correct |
7 ms |
8424 KB |
Output is correct |
8 |
Correct |
7 ms |
8556 KB |
Output is correct |
9 |
Correct |
7 ms |
8556 KB |
Output is correct |
10 |
Correct |
8 ms |
8580 KB |
Output is correct |
11 |
Correct |
7 ms |
8580 KB |
Output is correct |
12 |
Correct |
7 ms |
8580 KB |
Output is correct |
13 |
Correct |
7 ms |
8600 KB |
Output is correct |
14 |
Correct |
7 ms |
8652 KB |
Output is correct |
15 |
Correct |
8 ms |
8652 KB |
Output is correct |
16 |
Correct |
9 ms |
8652 KB |
Output is correct |
17 |
Correct |
8 ms |
8652 KB |
Output is correct |
18 |
Correct |
8 ms |
8652 KB |
Output is correct |
19 |
Correct |
8 ms |
8652 KB |
Output is correct |
20 |
Correct |
9 ms |
8652 KB |
Output is correct |
21 |
Correct |
8 ms |
8652 KB |
Output is correct |
22 |
Correct |
7 ms |
8652 KB |
Output is correct |
23 |
Correct |
7 ms |
8652 KB |
Output is correct |
24 |
Correct |
7 ms |
8652 KB |
Output is correct |
25 |
Correct |
10 ms |
9516 KB |
Output is correct |
26 |
Correct |
10 ms |
9536 KB |
Output is correct |
27 |
Correct |
10 ms |
9572 KB |
Output is correct |
28 |
Correct |
10 ms |
9636 KB |
Output is correct |
29 |
Correct |
10 ms |
9696 KB |
Output is correct |
30 |
Correct |
12 ms |
9696 KB |
Output is correct |
31 |
Correct |
9 ms |
9696 KB |
Output is correct |
32 |
Correct |
11 ms |
9736 KB |
Output is correct |
33 |
Correct |
9 ms |
9804 KB |
Output is correct |
34 |
Correct |
8 ms |
9804 KB |
Output is correct |
35 |
Correct |
9 ms |
9804 KB |
Output is correct |
36 |
Correct |
9 ms |
9804 KB |
Output is correct |
37 |
Correct |
9 ms |
9804 KB |
Output is correct |
38 |
Correct |
8 ms |
9808 KB |
Output is correct |
39 |
Correct |
8 ms |
9832 KB |
Output is correct |
40 |
Correct |
9 ms |
9832 KB |
Output is correct |
41 |
Correct |
9 ms |
9868 KB |
Output is correct |
42 |
Correct |
10 ms |
9888 KB |
Output is correct |
43 |
Incorrect |
10 ms |
9908 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8184 KB |
Output is correct |
2 |
Correct |
7 ms |
8288 KB |
Output is correct |
3 |
Correct |
7 ms |
8400 KB |
Output is correct |
4 |
Correct |
7 ms |
8400 KB |
Output is correct |
5 |
Correct |
8 ms |
8416 KB |
Output is correct |
6 |
Correct |
7 ms |
8420 KB |
Output is correct |
7 |
Correct |
7 ms |
8424 KB |
Output is correct |
8 |
Correct |
7 ms |
8556 KB |
Output is correct |
9 |
Correct |
7 ms |
8556 KB |
Output is correct |
10 |
Correct |
8 ms |
8580 KB |
Output is correct |
11 |
Correct |
7 ms |
8580 KB |
Output is correct |
12 |
Correct |
7 ms |
8580 KB |
Output is correct |
13 |
Correct |
7 ms |
8600 KB |
Output is correct |
14 |
Correct |
7 ms |
8652 KB |
Output is correct |
15 |
Correct |
8 ms |
8652 KB |
Output is correct |
16 |
Correct |
9 ms |
8652 KB |
Output is correct |
17 |
Correct |
8 ms |
8652 KB |
Output is correct |
18 |
Correct |
8 ms |
8652 KB |
Output is correct |
19 |
Correct |
8 ms |
8652 KB |
Output is correct |
20 |
Correct |
9 ms |
8652 KB |
Output is correct |
21 |
Correct |
8 ms |
8652 KB |
Output is correct |
22 |
Correct |
7 ms |
8652 KB |
Output is correct |
23 |
Correct |
7 ms |
8652 KB |
Output is correct |
24 |
Correct |
7 ms |
8652 KB |
Output is correct |
25 |
Correct |
10 ms |
9516 KB |
Output is correct |
26 |
Correct |
10 ms |
9536 KB |
Output is correct |
27 |
Correct |
10 ms |
9572 KB |
Output is correct |
28 |
Correct |
10 ms |
9636 KB |
Output is correct |
29 |
Correct |
10 ms |
9696 KB |
Output is correct |
30 |
Correct |
12 ms |
9696 KB |
Output is correct |
31 |
Correct |
9 ms |
9696 KB |
Output is correct |
32 |
Correct |
11 ms |
9736 KB |
Output is correct |
33 |
Correct |
9 ms |
9804 KB |
Output is correct |
34 |
Correct |
8 ms |
9804 KB |
Output is correct |
35 |
Correct |
9 ms |
9804 KB |
Output is correct |
36 |
Correct |
9 ms |
9804 KB |
Output is correct |
37 |
Correct |
9 ms |
9804 KB |
Output is correct |
38 |
Correct |
8 ms |
9808 KB |
Output is correct |
39 |
Correct |
8 ms |
9832 KB |
Output is correct |
40 |
Correct |
9 ms |
9832 KB |
Output is correct |
41 |
Correct |
9 ms |
9868 KB |
Output is correct |
42 |
Correct |
10 ms |
9888 KB |
Output is correct |
43 |
Incorrect |
10 ms |
9908 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |