Submission #1210996

#TimeUsernameProblemLanguageResultExecution timeMemory
1210996madamadam3Port Facility (JOI17_port_facility)C++20
22 / 100
2009 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int struct Event { int time, box_id; bool is_remove; const bool operator<(const Event &other) { return time < other.time; } }; const int MAXN = 1'000'001; const int MOD = 1'000'000'007; int n; int A[MAXN], B[MAXN]; vector<Event> events; int modexp(int a, int p) { if (p == 0) return 1; if (p == 1) return a; int ans = modexp(a, p / 2); ans %= MOD; ans *= ans; ans %= MOD; if (p % 2 == 1) ans *= a; ans %= MOD; return ans % MOD; } void solve() { int ways = 0; vector<vector<int>> adj(n, vector<int>()); set<pair<int,int>> active; // for (int i = 0; i < n; i++) { // for (int j = i+1; j < n; j++) { // int ci = i, cj = j; // if (A[ci] > A[cj]) swap(ci, cj); // if (A[ci] < A[cj] && A[cj] < B[ci] && B[ci] < B[cj]) { // adj[ci].push_back(cj); // adj[cj].push_back(ci); // } // } // } for (auto &E : events) { int idx = E.box_id; if (!E.is_remove) { auto it_lo = active.upper_bound({ A[idx], -1 }); auto it_hi = active.lower_bound({ B[idx], -1 }); vector<pair<int,int>> toLink; for (auto it = it_lo; it != it_hi; ++it) { toLink.push_back(*it); } for (auto &pr : toLink) { int other = pr.second; adj[other].push_back(idx); adj[idx].push_back(other); } active.insert({ B[idx], idx }); } else { active.erase({ B[idx], idx }); } } int cmps = 0; bool bipartite = true; vector<int> colour(n, -1); queue<int> q; for (int i = 0; i < n; i++) { if (colour[i] != -1 || !bipartite) continue; cmps++; q.push(i); colour[i] = 1; while (!q.empty()) { int cur = q.front(); q.pop(); for (auto &el : adj[cur]) { if (colour[el] == colour[cur]) { bipartite = false; break; } else if (colour[el] == -1) { colour[el] = colour[cur] == 1 ? 2 : 1; q.push(el); } } if (!bipartite) break; } } ways = bipartite ? modexp(2, cmps) % MOD : 0; cout << ways; } signed main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 0; i < n; i++) { cin >> A[i] >> B[i]; } for (int i = 0; i < n; i++) { events.push_back(Event {A[i], i, false}); events.push_back(Event {B[i], i, true}); } sort(events.begin(), events.end()); 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...