제출 #369248

#제출 시각아이디문제언어결과실행 시간메모리
369248fishy15Port Facility (JOI17_port_facility)C++14
0 / 100
1 ms492 KiB
#include <iostream> #include <iomanip> #include <fstream> #include <vector> #include <array> #include <algorithm> #include <utility> #include <map> #include <queue> #include <set> #include <cmath> #include <cstdio> #include <cstring> #define ll long long #define ld long double #define eps 1e-8 #define MOD 1000000007 #define INF 0x3f3f3f3f #define INFLL 0x3f3f3f3f3f3f3f3f // change if necessary #define MAXN 1000010 using namespace std; int n; pair<int, int> pts[MAXN]; int left_inv[2 * MAXN]; int right_inv[2 * MAXN]; int lmost[MAXN]; int rmost[MAXN]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) { int a, b; cin >> a >> b; pts[i] = {a, b}; left_inv[a] = i; right_inv[b] = i; } set<int> left, right; for (int i = 1; i <= 2 * n; i++) { if (left_inv[i]) { int c = left_inv[i]; if (right.empty()) { rmost[c] = 0; } else { auto it = right.lower_bound(pts[c].second); if (it == right.begin()) { rmost[c] = 0; } else { rmost[c] = *prev(it); } } left.insert(pts[c].first); right.insert(pts[c].second); } else { int c = right_inv[i]; left.erase(pts[c].first); right.erase(pts[c].second); if (left.empty()) { lmost[c] = INF; } else { auto it = left.upper_bound(pts[c].first); if (it == left.end()) { lmost[c] = INF; } else { lmost[c] = *it; } } } } for (int i = 1; i <= n; i++) { if (lmost[i] < rmost[i]) { cout << "0\n"; return 0; } } vector<int> stack; int ans_p = n; for (int i = 1; i <= 2 * n; i++) { if (left_inv[i]) { stack.push_back(left_inv[i]); } else { auto it = find(stack.begin(), stack.end(), right_inv[i]); ans_p -= stack.end() - it - 1; stack.erase(it); } } ll ans = 1; for (int i = 0; i < ans_p; i++) { ans += ans; if (ans >= MOD) ans -= MOD; } cout << ans << '\n'; 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...