제출 #928326

#제출 시각아이디문제언어결과실행 시간메모리
928326boris_mihovPort Facility (JOI17_port_facility)C++17
10 / 100
1 ms604 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <stack> #include <set> typedef long long llong; const int MAXN = 1e2 + 10; const int MOD = 1e9 + 7; const int INF = 1e9; int n; struct Fenwick { int tree[2 * MAXN]; void update(int pos, int val) { for (int idx = pos ; idx <= 2 * n ; idx += idx & (-idx)) { tree[idx] += val; } } int query(int pos) { int res = 0; for (int idx = pos ; idx > 0 ; idx -= idx & (-idx)) { res += tree[idx]; } return res; } }; int a[MAXN]; int b[MAXN]; int cnt[MAXN]; int minA[MAXN]; int maxB[MAXN]; int perm[MAXN]; std::set <int> s; int prefix[2 * MAXN]; std::pair <int,int> toSort[MAXN]; std::vector <std::pair <int,int>> queries[MAXN]; Fenwick tree; int vis[MAXN]; std::vector <int> g[MAXN]; bool dfs(int node) { for (const int &u : g[node]) { if (vis[u] == vis[node]) { return false; } if (vis[u] == 0) { vis[u] = 3 - vis[node]; if (!dfs(u)) return false; } } return true; } void solve() { std::sort(toSort + 1, toSort + 1 + n); for (int i = 1 ; i <= n ; ++i) { a[i] = toSort[i].first; b[i] = toSort[i].second; prefix[a[i]]++; } s.insert(0); for (int i = 1 ; i <= n ; ++i) { auto it = std::prev(s.upper_bound(b[i])); maxB[i] = *it; s.insert(b[i]); } std::iota(perm + 1, perm + 1 + n, 1); std::sort(perm + 1, perm + 1 + n, [&](int x, int y) { return b[x] > b[y]; }); s.clear(); s.insert(2 * n + 1); for (int i = 1 ; i <= n ; ++i) { auto it = s.upper_bound(a[perm[i]]); minA[perm[i]] = *it; s.insert(a[perm[i]]); } for (int i = 2 ; i < n ; ++i) { if (maxB[i] > minA[i]) { std::cout << 0 << '\n'; return; } } for (int i = 1 ; i <= 2 * n ; ++i) { prefix[i] += prefix[i - 1]; } for (int i = 1 ; i <= n ; ++i) { queries[i + 1].push_back({b[i], i}); queries[prefix[b[i]] + 1].push_back({b[i], -i}); } for (int i = n ; i >= 1 ; --i) { tree.update(b[i], 1); for (const auto &[biggerThan, idx] : queries[i]) { int curr = tree.query(2 * n) - tree.query(biggerThan); if (idx > 0) cnt[idx] += curr; else cnt[-idx] -= curr; } } int sum = 0; // for (int i = 1 ; i <= n ; ++i) // { // sum += cnt[i]; // } for (int i = 1 ; i <= n ; ++i) { for (int j = i + 1 ; j <= n ; ++j) { if (a[j] < b[i] && b[i] < b[j]) { g[i].push_back(j); g[j].push_back(i); // sum++; } } } int compCnt = 0; for (int i = 1 ; i <= n ; ++i) { if (!vis[i]) { vis[i] = 1; assert (dfs(i)); compCnt++; } } int ans = 1; assert(sum < n); for (int i = 0 ; i < compCnt ; ++i) { ans <<= 1; if (ans >= MOD) ans -= MOD; } std::cout << ans << '\n'; } void input() { std::cin >> n; for (int i = 1 ; i <= n ; ++i) { std::cin >> toSort[i].first >> toSort[i].second; } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { fastIOI(); input(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...