Submission #1015406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015406		MilosMilutinovic	Sky Walking (IOI19_walk)	C++14	100 / 100	2150 ms	218640 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();
  const int L = 20;
  vector<vector<int>> mx(n, vector<int>(L));
  for (int i = 0; i < n; i++) {
    mx[i][0] = h[i];
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
      mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
    }
  }
  vector<int> logs(n + 1);
  for (int i = 2; i <= n; i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  auto Query = [&](int L, int R) {
    int k = logs[R - L + 1];
    return max(mx[L][k], mx[R - (1 << k) + 1][k]);
  };
  auto FirstL = [&](int p, int h) {
    int low = 0, high = p, idx = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (Query(mid, p) >= h) {
        idx = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return idx;
  };
  auto FirstR = [&](int p, int h) {
    int low = p, high = n - 1, idx = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (Query(p, mid) >= h) {
        idx = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return idx;
  };
  vector<array<int, 3>> seg;
  for (int i = 0; i < m; i++) {
    seg.push_back({l[i], r[i], y[i]});
    if (l[i] < s && s < r[i]) {
      int p = FirstL(s, y[i]);
      int q = FirstR(s, y[i]);
      if (p != l[i]) {
        seg.push_back({l[i], p, y[i]});
      }
      if (p != q) {
        seg.push_back({p, q, y[i]});
      }
      if (q != r[i]) {
        seg.push_back({q, r[i], y[i]});
      }
    }
    if (l[i] < f && f < r[i]) {
      int p = FirstL(f, y[i]);
      int q = FirstR(f, y[i]);
      if (p != l[i]) {
        seg.push_back({l[i], p, y[i]});
      }
      if (p != q) {
        seg.push_back({p, q, y[i]});
      }
      if (q != r[i]) {
        seg.push_back({q, r[i], y[i]});
      }
    }
  }
  l.clear();
  r.clear();
  y.clear();
  m = (int) seg.size();
  for (int i = 0; i < m; i++) {
    l.push_back(seg[i][0]);
    r.push_back(seg[i][1]);
    y.push_back(seg[i][2]);
  }
  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: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43