제출 #388609

#제출 시각아이디문제언어결과실행 시간메모리
388609ParsaAlizadehRoller Coaster Railroad (IOI16_railroad)C++17
0 / 100
177 ms8328 KiB
#include <bits/stdc++.h> #include "railroad.h" using namespace std; typedef long long ll; struct DSU { int n; vector<int> par; DSU(int n) : n(n), par(n, -1) {} int find(int u) { return par[u] == -1 ? u : par[u] = find(par[u]); } bool merge(int u, int v) { u = find(u); v = find(v); if (u == v) return false; par[v] = u; return true; } }; ll plan_roller_coaster(vector<int> s, vector<int> t) { int const n = (int) s.size(); vector<int> comp(begin(s), end(s)); comp.insert(end(comp), begin(t), end(t)); sort(begin(comp), end(comp)); comp.erase(unique(begin(comp), end(comp)), end(comp)); int const m = (int) comp.size(); vector<int> ps(m); DSU dsu(m); ll ans = 0; for (int i = 0; i < n; i++) { int l = lower_bound(begin(comp), end(comp), s[i]) - begin(comp); int r = lower_bound(begin(comp), end(comp), t[i]) - begin(comp); ps[l]++; ps[r]--; dsu.merge(l, r); } ps[m - 1]++; ps[0]--; for (int i = 0; i + 1 < m; i++) { if (ps[i] > 0) ans += (ll) ps[i] * (comp[i + 1] - comp[i]); if (ps[i] != 0) dsu.merge(i, i + 1); } for (int i = 0; i + 1 < m; i++) { if (dsu.merge(i, i + 1)) ans += comp[i + 1] - comp[i]; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...