Submission #1015375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015375		MilosMilutinovic	Sky Walking (IOI19_walk)	C++14	33 / 100	1227 ms	126604 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int f) {
  int n = (int) x.size();
  int m = (int) y.size();
  vector<pair<int, int>> ver;
  for (int i = 0; i < n; i++) {
    ver.emplace_back(i, 0);
    ver.emplace_back(i, h[i]);
  }
  for (int i = 0; i < m; i++) {
    ver.emplace_back(l[i], y[i]);
    ver.emplace_back(r[i], y[i]);
  }
  vector<vector<int>> qs(n);
  for (int i = 0; i < m; i++) {
    qs[l[i]].push_back(y[i]);
    qs[r[i]].push_back(~y[i]);
  }
  multiset<int> st;
  for (int i = 0; i < n; i++) {
    for (int j : qs[i]) {
      if (j >= 0) {
        auto it = st.lower_bound(j);
        if (it != st.end()) {
          ver.emplace_back(i, *it);
        }
        if (it != st.begin()) {
          ver.emplace_back(i, *prev(it));
        }
        st.insert(j);
      }
    }
    for (int j : qs[i]) {
      if (j < 0) {
        j = ~j;
        auto it = st.lower_bound(j);
        if (it != prev(st.end())) {
          ver.emplace_back(i, *next(it));
        }
        if (it != st.begin()) {
          ver.emplace_back(i, *prev(it));
        }
        st.erase(it);
      }
    }
  }
  vector<pair<int, int>> new_ver;
  for (auto& p : ver) {
    if (h[p.first] >= p.second) {
      new_ver.push_back(p);
    }
  }
  ver = new_ver;
  sort(ver.begin(), ver.end());
  ver.erase(unique(ver.begin(), ver.end()), ver.end());
  auto Index = [&](int i, int h) {
    return (int) (lower_bound(ver.begin(), ver.end(), make_pair(i, h)) - ver.begin());
  };
  int k = (int) ver.size();
  vector<vector<pair<int, int>>> g(k);
  auto Add = [&](int from, int to, int cost) {
    g[from].emplace_back(to, cost);
    g[to].emplace_back(from, cost);
  };
  for (int i = 0; i + 1 < k; i++) {
    if (ver[i + 1].first == ver[i].first) {
      Add(i, i + 1, ver[i + 1].second - ver[i].second);
    }
  }
  map<int, vector<int>> mp;
  for (int i = 0; i < k; i++) {
    mp[ver[i].second].push_back(i);
  }
  for (auto& p : mp) {
    sort(p.second.begin(), p.second.end(), [&](int i, int j) {
      return ver[i].first < ver[j].first;
    });
  }
  for (int i = 0; i < m; i++) {
    int low = 0, high = (int) mp[y[i]].size() - 1, pos = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (ver[mp[y[i]][mid]].first >= l[i]) {
        pos = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    while (ver[mp[y[i]][pos]].first != r[i]) {
      Add(mp[y[i]][pos], mp[y[i]][pos + 1], x[ver[mp[y[i]][pos + 1]].first] - x[ver[mp[y[i]][pos]].first]);
      pos += 1;
    }
  }
  const long long inf = (long long) 1e18;
  vector<long long> dist(k, inf);
  dist[Index(s, 0)] = 0;
  set<pair<long long, int>> que;
  que.emplace(0, Index(s, 0));
  while (!que.empty()) {
    auto it = que.begin();
    int i = it->second;
    que.erase(it);
    for (auto &e : g[i]) {
      int to = e.first;
      int w = e.second;
      if (dist[to] > dist[i] + w) {
        if (dist[to] != inf) {
          que.erase({dist[to], to});
        }
        dist[to] = dist[i] + w;
        que.emplace(dist[to], to);
      }
    }
  }
  long long res = dist[Index(f, 0)];
  if (res == inf) {
    return -1;
  } else {
    return res;
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43