Submission #1242709

#TimeUsernameProblemLanguageResultExecution timeMemory
1242709BoasSky Walking (IOI19_walk)C++20
0 / 100
17 ms3400 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; #define int long long #define loop(n, i) for (int i = 0; i < n; i++) #define pb push_back #define sz(x) (int)(x).size() typedef pair<int, int> ii; typedef vector<int32_t> vi32; typedef vector<ii> vii; typedef vector<vii> vvii; typedef set<ii> sii; typedef long long i64; typedef vector<i64> vi64; typedef vector<vi64> vvi64; typedef vector<vi32> vvi32; i64 INF = 1e18; i64 min_distance(vi32 x, vi32 h, vi32 l, vi32 r, vi32 y, int32_t s, int32_t g) { int n = sz(x), m = sz(l); vvi32 endsHere(n), startHere(n); loop(m, i) endsHere[r[i]].pb(i); loop(m, i) startHere[l[i]].pb(i); vi64 dis(m, INF); sii active; // {y, ix} i64 res = INF; for (int p = 0; p < n; p++) { for (int i : startHere[p]) { int y2 = y[i]; auto nxt = active.lower_bound({y2, 0}); if (nxt != active.end()) { auto [y1, j] = *nxt; dis[i] = min(dis[i], dis[j] + abs(y1 - y2)); } if (nxt != begin(active)) { auto [y1, j] = *--nxt; dis[i] = min(dis[i], dis[j] + abs(y1 - y2)); } } for (int i : startHere[p]) { active.insert({y[i], i}); if (p == 0) dis[i] = y[i]; } if (p == g) { for (auto [y1, i] : active) { res = min(res, dis[i] + y1); } } for (int i : endsHere[p]) { active.erase({y[i], i}); } } if (res == INF) return -1; return res + x.back(); }
#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...