#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
#define SZ(x) ((int)x.size())
const int N = (int)1e6+5;
const int base = (int)1e9+7;
int n, vis[N], lo[N], hi[N];
ii tree[3][1 << 21], a[N];
void merge_tree(ii tr[], int root, int lf, int rt) {
if (tr[lf].first < tr[rt].first)
tr[root] = tr[rt];
else tr[root] = tr[lf];
}
void build(ii tr[], int k, int l, int r) {
if (l > r) return;
if (l == r) {
tr[k].first = a[l].second, tr[k].second = l;
return;
}
int mid = (l + r) >> 1;
build(tr, k << 1, l, mid);
build(tr, k << 1 | 1, mid + 1, r);
merge_tree(tr, k, k << 1, k << 1 | 1);
}
void update(ii tr[], int k, int l, int r, int pos, const ii &val) {
if (l > r || l > pos || r < pos) return;
if (l == r && l == pos) {
tr[k] = val;
return;
}
int mid = (l + r) >> 1;
update(tr, k << 1, l, mid, pos, val);
update(tr, k << 1 | 1, mid + 1, r, pos, val);
merge_tree(tr, k, k << 1, k << 1 | 1);
}
ii query(ii tr[], int k, int l, int r, int L, int R) {
if (l > r || l > R || r < L) return ii(0, 0);
if (L <= l && r <= R) return tr[k];
int mid = (l + r) >> 1;
ii lf = query(tr, k << 1, l, mid, L, R);
ii rt = query(tr, k << 1 | 1, mid + 1, r, L, R);
if (lf.first < rt.first) return rt;
return lf;
}
bool check(int idx, int id) {
ii tmp = query(tree[id], 1, 1, n, lo[idx], hi[idx]);
return tmp.first <= a[idx].second;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].first, &a[i].second);
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
lo[i] = i;
hi[i] = upper_bound(a + i, a + n + 1, ii(a[i].second, 0)) - a - 1;
}
build(tree[0], 1, 1, n);
int ans = 1;
for (int i = 1; i <= n; ++i) if (!vis[i]) {
queue<int> q;
q.push(i);
vis[i] = 1;
update(tree[0], 1, 1, n, i, ii(0, 0));
while (SZ(q)) {
int u = q.front(); q.pop();
update(tree[vis[u]], 1, 1, n, u, ii(a[u].second, u));
if (!check(u, vis[u])) return printf("0"), 0;
ii tmp = query(tree[0], 1, 1, n, lo[u], hi[u]);
while (tmp.first > a[u].second) {
vis[tmp.second] = 3 - vis[u];
q.push(tmp.second);
update(tree[0], 1, 1, n, tmp.second, ii(0, 0));
tmp = query(tree[0], 1, 1, n, lo[u], hi[u]);
}
}
ans = ans * 2 % base;
}
printf("%d", ans);
return 0;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:66:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
port_facility.cpp:67:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].first, &a[i].second);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
