제출 #145196

#제출 시각아이디문제언어결과실행 시간메모리
145196ecnerwalaSky Walking (IOI19_walk)C++14
100 / 100
1547 ms133740 KiB
#include "walk.h" #include<bits/stdc++.h> namespace { namespace min_distance_set { using namespace std; using ll = long long; using height_t = pair<ll, int>; const ll INF = 1e18; struct height_container { set<height_t> alive; map<height_t, ll> value; ll query(height_t h) { ll ans = INF; auto it = value.lower_bound(h); if (it != value.end()) { ans = min(ans, it->second + abs(h.first - it->first.first)); } if (it != value.begin()) { --it; ans = min(ans, it->second + abs(h.first - it->first.first)); } return ans; } void insert_line(height_t h, ll v = INF) { assert(!alive.count(h)); alive.insert(h); if (v == INF || v >= query(h)) { return; } assert(!value.count(h)); auto emp = value.emplace(h, v); assert(emp.second); while (true) { auto it = emp.first; ++it; if (it == value.end()) break; if (it->second >= emp.first->second + abs(it->first.first - emp.first->first.first)) { value.erase(it); } else { break; } } while (true) { auto it = emp.first; if (it == value.begin()) break; --it; if (it->second >= emp.first->second + abs(it->first.first - emp.first->first.first)) { value.erase(it); } else { break; } } } void delete_line(height_t h) { assert(alive.count(h)); if (value.count(h)) { auto pt = alive.find(h); auto nt = pt; if (pt != alive.begin()) { --pt; ll v = query(*pt); value.emplace(*pt, v); } if (nt != alive.end()) { ++nt; if (nt != alive.end()) { ll v = query(*nt); value.emplace(*nt, v); } } value.erase(h); } alive.erase(h); } void insert_all(vector<height_t> v) { for (height_t h : v) insert_line(h); } void delete_all(vector<height_t> v) { for (height_t h : v) delete_line(h); } friend std::ostream& operator << (std::ostream& o, const height_container& h) { o << "["; for (const auto& it : h.alive) { o << "(" << it.first << "," << it.second << ")"; o << ": "; if (h.value.count(it)) { o << h.value.at(it); } else { o << "_"; } o << ", "; } o << "]"; return o; } }; ll min_distance(vector<int> X_, vector<int> H_, vector<int> L, vector<int> R, vector<int> Y_, int S, int T) { int N = int(X_.size()); int M = int(Y_.size()); vector<ll> X(X_.begin(), X_.end()); vector<height_t> H(N); for (int i = 0; i < N; i++) { H[i] = {H_[i], i}; } vector<height_t> Y(M); for (int e = 0; e < M; e++) { Y[e] = {Y_[e], -1-e}; } if (S > T) swap(S, T); assert(S < T); // peak index int P = int(max_element(H.begin() + S, H.begin() + T + 1) - H.begin()); assert(H[P] >= H[S] && H[P] >= H[T]); const height_t BOTTOM = {0, -M-1}; const height_t TOP = {INF, N}; vector<vector<height_t>> lefts(N); vector<vector<height_t>> rights(N); for (int e = 0; e < M; e++) { lefts[L[e]].push_back(Y[e]); rights[R[e]].push_back(Y[e]); } priority_queue<height_t, vector<height_t>, greater<height_t>> highEdges; for (int e = 0; e < M; e++) { highEdges.push(Y[e]); } if (false) { // left->right only if (S == 0 && T == N-1) { height_container hc; hc.insert_line(BOTTOM, 0); rights[S].push_back(BOTTOM); lefts[T].push_back(BOTTOM); for (int i = 0; i < N; i++) { hc.insert_all(lefts[i]); hc.delete_all(rights[i]); } ll ans = hc.query(BOTTOM); if (ans == INF) { return -1; } return ans + (X[T] - X[S]); } else { return -2; } } height_container sLeft, sRight, tLeft, tRight; sLeft.insert_line({0, -M-1}, 0); sRight.insert_line({0, -M-1}, 0); tLeft.insert_line({0, -M-1}, 0); tRight.insert_line({0, -M-1}, 0); lefts[S].push_back({0, -M-1}); rights[S].push_back({0, -M-1}); lefts[T].push_back({0, -M-1}); rights[T].push_back({0, -M-1}); int sl = S, sr = S, tl = T, tr = T; ll ans = INF; bool crossedMid = false; while (true) { height_t evtHeight = TOP; if (!highEdges.empty()) { evtHeight = min(evtHeight, highEdges.top()); } if (sl > 0) { evtHeight = min(evtHeight, H[sl]); } if (!crossedMid) { evtHeight = min(evtHeight, H[sr]); evtHeight = min(evtHeight, H[tl]); } if (tr < N-1) { evtHeight = min(evtHeight, H[tr]); } if (evtHeight == TOP) break; if (!highEdges.empty() && evtHeight == highEdges.top()) { // do the thing int e = -1-highEdges.top().second; highEdges.pop(); if (crossedMid) { assert(Y[e] > H[P]); assert(L[e] < S || L[e] > T); assert(R[e] < S || R[e] > T); if (L[e] < P && P < R[e]) { // just connect the two, it crosses ans = min(ans, sLeft.query(Y[e]) + tRight.query(Y[e]) + 2 * (X[S] - X[sl]) + 2 * (X[tr] - X[T])); // it's never optimal to go further, so we could just break //break; sLeft.insert_line(Y[e]); tRight.insert_line(Y[e]); } } else { assert(Y[e] <= H[P]); if (L[e] <= S && S <= R[e]) { ll rval = sRight.query(Y[e]) + 2 * (X[sr] - X[S]); ll lval = sLeft.query(Y[e]) + 2 * (X[S] - X[sl]); sLeft.insert_line(Y[e], rval); sRight.insert_line(Y[e], lval); } if (L[e] <= T && T <= R[e]) { ll rval = tRight.query(Y[e]) + 2 * (X[tr] - X[T]); ll lval = tLeft.query(Y[e]) + 2 * (X[T] - X[tl]); tLeft.insert_line(Y[e], rval); tRight.insert_line(Y[e], lval); } } } else if (!crossedMid && evtHeight == H[P]) { assert(sr == P && tl == P); for (auto it : sRight.value) { ans = min(ans, it.second + tLeft.query(it.first)); } crossedMid = true; } else if (sl > 0 && evtHeight == H[sl]) { sLeft.delete_all(lefts[sl]); --sl; sLeft.insert_all(rights[sl]); } else if (sr < P && evtHeight == H[sr]) { sRight.delete_all(rights[sr]); ++sr; sRight.insert_all(lefts[sr]); } else if (tl > P && evtHeight == H[tl]) { tLeft.delete_all(lefts[tl]); --tl; tLeft.insert_all(rights[tl]); } else if (tr < N-1 && evtHeight == H[tr]) { tRight.delete_all(rights[tr]); ++tr; tRight.insert_all(lefts[tr]); } else assert(false); } //cerr << ans << '\n'; if (ans == INF) return -1; else return ans + (X[T] - X[S]); } } // namespace min_distance_set namespace min_distance_dijk { using namespace std; using ll = long long; using height_t = pair<int, int>; ll min_distance(vector<int> X_, vector<int> H_, vector<int> L, vector<int> R, vector<int> Y_, int S, int T) { int N = int(X_.size()); int M = int(Y_.size()); vector<ll> X(X_.begin(), X_.end()); vector<height_t> H(N); for (int i = 0; i < N; i++) { H[i] = {H_[i], i}; } vector<height_t> Y(M); for (int e = 0; e < M; e++) { Y[e] = {Y_[e], -1-e}; } vector<vector<height_t>> needs(N); vector<height_t> heights; heights.insert(heights.end(), H.begin(), H.end()); heights.insert(heights.end(), Y.begin(), Y.end()); sort(heights.begin(), heights.end()); reverse(heights.begin(), heights.end()); set<int> posts; for (height_t h : heights) { if (h.second >= 0) { // it's a post posts.insert(h.second); } else { int e = -1-h.second; set<int> eNeeds; eNeeds.insert(L[e]); eNeeds.insert(R[e]); for (int p : {S, T}) { if (L[e] <= p && p <= R[e]) { { auto it = posts.lower_bound(p); if (it != posts.end()) { eNeeds.insert(*it); } } { auto it = posts.upper_bound(p); if (it != posts.begin()) { eNeeds.insert(*--it); } } } } for (int i : eNeeds) { needs[i].push_back(h); } } } int V = 0; vector<vector<pair<int, ll>>> adj; map<height_t, pair<int, int>> prvVert; set<height_t> inters; vector<vector<height_t>> lefts(N); vector<vector<height_t>> rights(N); for (int e = 0; e < M; e++) { lefts[L[e]].push_back(Y[e]); rights[R[e]].push_back(Y[e]); } const height_t SBOTTOM(0, -1-M); lefts[S].push_back(SBOTTOM); rights[S].push_back(SBOTTOM); needs[S].push_back(SBOTTOM); const height_t TBOTTOM(0, -1-(M+1)); lefts[T].push_back(TBOTTOM); rights[T].push_back(TBOTTOM); needs[T].push_back(TBOTTOM); int Svert = -1, Tvert = -1; for (int i = 0; i < N; i++) { for (height_t h : lefts[i]) { inters.insert(h); } reverse(needs[i].begin(), needs[i].end()); // should now be sorted vector<height_t> realNeeds; for (height_t h : needs[i]) { auto it = inters.find(h); assert(it != inters.end()); auto kt = it; if (kt != inters.begin()) { --kt; if (realNeeds.empty() || realNeeds.back() < *kt) { realNeeds.push_back(*kt); } } if (realNeeds.empty() || realNeeds.back() < *it) { realNeeds.push_back(*it); } auto jt = it; ++jt; if (jt != inters.end()) { if (realNeeds.empty() || realNeeds.back() < *jt) { realNeeds.push_back(*jt); } } } while (!realNeeds.empty() && realNeeds.back() > H[i]) realNeeds.pop_back(); assert(V == int(adj.size())); adj.resize(V + int(realNeeds.size())); for (int z = 0; z < int(realNeeds.size()); z++) { height_t h = realNeeds[z]; int v = V + z; auto it = prvVert.find(h); if (it != prvVert.end()) { int u = it->second.second; ll d = X[i] - X[it->second.first]; adj[v].emplace_back(u, d); adj[u].emplace_back(v, d); it->second = {i, v}; } else { prvVert.emplace(h, pair<int, int>{i, v}); } } for (int z = 0; z+1 < int(realNeeds.size()); z++) { assert(realNeeds[z] < realNeeds[z+1]); int v = V + z + 1; int u = V + z; ll d = realNeeds[z+1].first - realNeeds[z].first; adj[v].emplace_back(u, d); adj[u].emplace_back(v, d); } if (i == S) { assert(!realNeeds.empty()); assert(realNeeds[0] == SBOTTOM); Svert = V + 0; } if (i == T) { assert(!realNeeds.empty()); assert(realNeeds[0] == TBOTTOM); Tvert = V + 0; } V += int(realNeeds.size()); for (height_t h : rights[i]) { inters.erase(h); } } const ll INF = 1e18; vector<ll> dist(V, INF); priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; dist[Svert] = 0; pq.emplace(0, Svert); while (!pq.empty()) { int cur = pq.top().second; ll d = pq.top().first; pq.pop(); if (dist[cur] != d) continue; if (cur == Tvert) return d; for (auto it : adj[cur]) { int nxt = it.first; ll nd = d + it.second; if (nd < dist[nxt]) { dist[nxt] = nd; pq.emplace(nd, nxt); } } } return -1; } } // namespace min_distance_dijk } // anonymous namespace long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int S, int T) { if (false) { return min_distance_set::min_distance(X, H, L, R, Y, S, T); } else { return min_distance_dijk::min_distance(X, H, L, R, Y, S, T); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...