Submission #607495

#TimeUsernameProblemLanguageResultExecution timeMemory
607495TemmieSky Walking (IOI19_walk)C++17
100 / 100
1571 ms379196 KiB
#include <bits/stdc++.h> struct SG { int h, l, r; SG() { } SG(int a, int b, int c) : h(a) , l(b) , r(c) { } }; int n, m; std::vector <std::pair <int, int>> g[2]; std::vector <std::vector <std::pair <int, int>>> gg; std::vector <std::vector <int>> del[2]; std::vector <int> h; std::vector <SG> sg; void fix(int node) { std::vector <std::pair <int, int>> dir[2]; dir[0] = dir[1] = { { h[node], node } }; for (int i = node + 1; i < n; i++) { if (h[i] <= dir[1].back().first) { continue; } dir[1].emplace_back(h[i], i); } for (int i = node - 1; i >= 0; i--) { if (h[i] <= dir[0].back().first) { continue; } dir[0].emplace_back(h[i], i); } auto cop = sg; cop.clear(); for (const auto& s : sg) { if (s.l < node && node < s.r) { int lb[2] = { (int) (std::lower_bound(dir[0].begin(), dir[0].end(), std::make_pair(s.h, -1)) - dir[0].begin()), (int) (std::lower_bound(dir[1].begin(), dir[1].end(), std::make_pair(s.h, -1)) - dir[1].begin()) }; if (s.l != dir[0][lb[0]].second) { cop.emplace_back(s.h, s.l, dir[0][lb[0]].second); } if (dir[0][lb[0]].second != dir[1][lb[1]].second) { cop.emplace_back(s.h, dir[0][lb[0]].second, dir[1][lb[1]].second); } if (dir[1][lb[1]].second != s.r) { cop.emplace_back(s.h, dir[1][lb[1]].second, s.r); } } else { cop.emplace_back(s); } } sg = cop; } long long min_distance(std::vector <int> a, std::vector <int> _h, std::vector <int> l, std::vector <int> r, std::vector <int> y, int f, int t) { n = a.size(); m = l.size(); sg.resize(m); h = _h; for (int i = 0; i < m; i++) { sg[i] = { y[i], l[i], r[i] }; } fix(f); fix(t); del[0].resize(4'000'000); del[1].resize(4'000'000); for (const auto& s : sg) { del[0][s.l].emplace_back(s.h); del[1][s.r].emplace_back(s.h); } std::multiset <int> st = { 0 }; for (int i = 0; i < n; i++) { for (int x : del[0][i]) { st.insert(x); } for (int k = 0; k < 2; k++) { for (int x : del[k][i]) { g[0].emplace_back(a[i], x); g[0].emplace_back(a[i], *prev(st.lower_bound(x))); } } for (int x : del[1][i]) { st.erase(st.find(x)); } } std::sort(g[0].begin(), g[0].end()); for (auto p : g[0]) { if (g[1].empty() || g[1].back() != p) { g[1].push_back(p); } } g[0] = g[1]; g[1].clear(); for (auto p : g[0]) { g[1].emplace_back(p.second, p.first); } std::sort(g[1].begin(), g[1].end()); gg.resize(4'000'000); for (int i = 1; i < (int) g[0].size(); i++) { if (g[0][i - 1].first != g[0][i].first) { continue; } gg[i - 1].emplace_back(i - 0, g[0][i].second - g[0][i - 1].second); gg[i - 0].emplace_back(i - 1, g[0][i].second - g[0][i - 1].second); } for (const auto& s : sg) { int lb = std::lower_bound(g[1].begin(), g[1].end(), std::make_pair(s.h, a[s.l])) - g[1].begin(); while (g[1][lb] != (std::pair <int, int>) { s.h, a[s.r] }) { std::pair <int, int> p[2] = { { g[1][lb - 0].second, g[1][lb - 0].first }, { g[1][lb + 1].second, g[1][lb + 1].first } }; lb++; gg[std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin(), p[1].first - p[0].first); gg[std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin(), p[1].first - p[0].first); } } std::vector <long long> dd(4'000'000, 1LL << 60); std::priority_queue <std::pair <long long, int>> pq; { int tmp = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[f], 0)) - g[0].begin(); if (tmp == (int) g[0].size() || g[0][tmp] != (std::pair <int, int>) { a[f], 0 }) { return -1; } pq.push({ dd[tmp] = 0, tmp }); } while (pq.size()) { int v = pq.top().second; pq.pop(); for (auto p : gg[v]) { if (dd[p.first] <= dd[v] + p.second) { continue; } dd[p.first] = dd[v] + p.second; pq.push({ -dd[p.first], p.first }); } } int lb = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[t], 0)) - g[0].begin(); return lb == (int) g[0].size() || g[0][lb] != (std::pair <int, int>) { a[t], 0 } || dd[lb] == (1LL << 60) ? -1LL : dd[lb]; }
#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...