Submission #1211185

#TimeUsernameProblemLanguageResultExecution timeMemory
1211185madamadam3Port Facility (JOI17_port_facility)C++20
100 / 100
1440 ms180316 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct DSU { int n; vector<int> par, siz; vector<vector<int>> adj; DSU(int N) { n = N; par.resize(n); iota(par.begin(), par.end(), 0); siz.assign(n, 1); adj.assign(n, vector<int>()); } int find(int v) { if (par[v] == v) return v; return par[v] = find(par[v]); } void unite(int a, int b) { int oa = a, ob = b; a = find(a); b = find(b); if (a != b) { if (siz[a] < siz[b]) swap(a, b); par[b] = a; siz[a] += siz[b]; adj[oa].push_back(ob); adj[ob].push_back(oa); } } }; struct Fenw { int n; vector<int> bit; Fenw(int N) { n = N; bit.assign(n, 0); } void update(int idx, int delta) { while (idx < n) { bit[idx] += delta; idx = idx | (idx + 1); } } int query(int r) { int res = 0; while (r >= 0) { res += bit[r]; r = (r & (r + 1)) - 1; } return res; } int query(int l, int r) { return query(r) - query(l - 1); } }; 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; vector<int> ord; ll modexp(ll a, ll p) { if (p == 0) return 1; if (p == 1) return a; ll ans = modexp(a, p / 2) % MOD; ans = (ans * ans) % MOD; if (p % 2 == 1) ans = (ans * a) % MOD; return ans % MOD; } void solve() { int ways = 1; vector<int> groups(n, -1); auto dsu = DSU(n); // step (1) construct the DSU using line sweep std::set<pair<int, int>> st; for (int idx = 0; idx < n; idx++) { int i = ord[idx]; int L = A[i], R = B[i]; while(!st.empty() && st.begin()->first < L) st.erase(st.begin()); auto itL = st.lower_bound({L, -1}), itR = st.lower_bound({R, -1}); if(itL != itR){ auto last = std::prev(itR); while(true) { int j = itL->second; dsu.unite(i, j); if(dsu.find(itL->second) == dsu.find(last->second)) break; ++itL; } } st.insert({R, i}); } // step (2) make an initial colouring of the graph set<int> heads; for (int i = 0; i < n; i++) { heads.insert(dsu.find(i)); if (groups[dsu.find(i)] != -1) continue; queue<int> q; q.push(dsu.find(i)); groups[dsu.find(i)] = 1; while (!q.empty()) { int cur = q.front(); q.pop(); for (auto &v : dsu.adj[cur]) { if (groups[v] == -1) { groups[v] = groups[cur] == 1 ? 2 : 1; q.push(v); } else if (groups[v] == groups[cur]) { cout << 0; return; } } } } // step (3) re-add every edge, but check if the 2 nodes have the same colour, if they do exit Fenw white = Fenw(2*n+2), black = Fenw(2*n+2); for (auto &evt : events) { bool remove = evt.is_remove; int box = evt.box_id; if (!remove) { (groups[box] == 1 ? white : black).update(A[box], 1); } else { (groups[box] == 1 ? white : black).update(B[box], -1); int diff = (groups[box] == 1 ? white : black).query(A[box], B[box]); if (diff != 0) { cout << 0; return; } } } int cmps = heads.size(); ways = modexp(2, cmps); // either group 1 in A g2 B or g1 B g2 A so 2 ways for each cmp 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()); ord.resize(n); iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(), [&](int i,int j){ return A[i] < A[j]; }); 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...