Submission #418658

#	Time	Username	Problem	Language	Result	Execution time	Memory
418658		usachevd0	Sky Walking (IOI19_walk)	C++17	100 / 100	1759 ms	225932 KiB

walk

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef LOCAL
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
  for (auto& e : v) {
    stream << e << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}


const ll INF64 = 1e18;
#ifdef LOCAL
  const int maxN = 50;
  const int maxV = 150;
#else
  const int maxN = 1e5 + 5;
  const int maxV = 4e6 + 6;
#endif
int n, m;

int V;
vector<pii> G[maxV];
ll dist[maxV];
priority_queue<pli> pq;

set<int> points[maxN];
map<int, int> ptIdx[maxN];
int getIdx(int i, int y) {
  if (ptIdx[i].count(y))
    return ptIdx[i][y];
  return ptIdx[i][y] = V++;
}

void addEdge(int u, int v, int w) {
  G[u].emplace_back(v, w);
  G[v].emplace_back(u, w);
}

namespace sgt {
  const int logN = 17;
  const int N = 1 << logN;
  int mx[2 * N];
  
  void build(vector<int>& H) {
    for (int i = 0; i < n; ++i)
      mx[i + N] = H[i];
    for (int i = N - 1; i >= 1; --i)
      mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
  }
  
  int getFirstGeq(int v, int vl, int vr, int l, int r, int x) {
    if (l > r || vr < l || r < vl || mx[v] < x) return -1;
    if (vl == vr) return vl;
    int vm = (vl + vr) >> 1;
    int al = getFirstGeq(v << 1, vl, vm, l, r, x);
    if (al != -1)
      return al;
    return getFirstGeq(v << 1 | 1, vm + 1, vr, l, r, x);
  }
  int getFirstGeq(int l, int r, int x) {
    return getFirstGeq(1, 0, N - 1, l, r, x);
  }
  
  int getLastGeq(int v, int vl, int vr, int l, int r, int x) {
    if (l > r || vr < l || r < vl || mx[v] < x) return -1;
    if (vl == vr) return vl;
    int vm = (vl + vr) >> 1;
    int ar = getLastGeq(v << 1 | 1, vm + 1, vr, l, r, x);
    if (ar != -1)
      return ar;
    return getLastGeq(v << 1, vl, vm, l, r, x);
  }
  int getLastGeq(int l, int r, int x) {
    return getLastGeq(1, 0, N - 1, l, r, x);
  }
}

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int si, int ti) {
  n = X.size(), m = L.size();
  int S, T;
  for (int i = 0; i < n; ++i) {
    int v = getIdx(i, 0);
    if (i == si)
      S = v;
    if (i == ti)
      T = v;
  }
  sgt::build(H);
  struct Event {
    int i, tp, j;
    
    Event() {}
    Event(int _i, int _tp, int _j): i(_i), tp(_tp), j(_j) {}
    
    bool operator < (const Event& e) const {
      if (i != e.i)
        return i < e.i;
      return tp < e.tp;
    }
  };
  vector<Event> ev;
  for (int j = 0; j < m; ++j) {
    int l = L[j], r = R[j], y = Y[j];
    auto& p = points[j];
    p.insert(l);
    p.insert(r);
    for (int i : {si, ti}) {
      if (i <= r)
        p.insert(sgt::getFirstGeq(max(l, i), r, y));
      if (i >= l)
        p.insert(sgt::getLastGeq(l, min(r, i), y));
    }
    ev.emplace_back(l + 1, 0, j);
    ev.emplace_back(r, 1, j);
    for (int i : p)
      ev.emplace_back(i, 2, j);
  }
  sort(all(ev));
  set<pii> open;
  for (auto& e : ev) {
    if (e.tp == 0) {
      open.insert({Y[e.j], e.j});
    } else if (e.tp == 1) {
      open.erase({Y[e.j], e.j});
    } else {
      int y = Y[e.j];
      // debug(e.i, y, e.j);
      // for (auto el : open) cerr << el << ";  "; cerr << endl;
      auto it = open.lower_bound({y, -1});
      if (it != open.begin()) {
        it = prev(it);
        int y1 = it->fi;
        int j1 = it->se;
        getIdx(e.i, y1);
        points[j1].insert(e.i);
      }
    }
  }
  for (int j = 0; j < m; ++j) {
    // debug(j);
    // for (auto i : points[j])
    //   cerr << i << ' ';
    // cerr << endl;
    int y = Y[j];
    int last_i = -1;
    int last_v = -1;
    for (int i : points[j]) {
      int v = getIdx(i, y);
      if (last_i != -1) {
        addEdge(last_v, v, X[i] - X[last_i]);
      }
      last_i = i;
      last_v = v;
    }
  }
  for (int i = 0; i < n; ++i) {
    int last_v = -1;
    int last_y = -1;
    // debug(i);
    for (auto& [y, v] : ptIdx[i]) {
      // cerr << y << ' ';
      if (last_v != -1) {
        addEdge(last_v, v, y - last_y);
      }
      last_v = v;
      last_y = y;
    }
    // cerr << endl;
  }
  fill(dist, dist + V, INF64);
  dist[S] = 0;
  pq.push({0, S});
  while (!pq.empty()) {
    int v = pq.top().se;
    ll d = -pq.top().fi;
    pq.pop();
    if (d != dist[v]) continue;
    if (v == T) return dist[v];
    for (auto& [u, w] : G[v])
      if (chkmin(dist[u], dist[v] + w))
        pq.push({-dist[u], u});
  }
  return -1;
}


#ifdef LOCAL
int32_t main() {
  #ifdef LOCAL
    freopen("in", "r", stdin);
  #endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int n, m;
  assert(2 == scanf("%d%d", &n, &m));
  vector<int> x(n), h(n);
  for (int i = 0; i < n; i++)
    assert(2 == scanf("%d%d", &x[i], &h[i]));
  vector<int> l(m), r(m), y(m);
  for (int i = 0; i < m; i++)
    assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
  int s, g;
  assert(2 == scanf("%d%d", &s, &g));
  fclose(stdin);

  long long result = min_distance(x, h, l, r, y, s, g);

  printf("%lld\n", result);
  fclose(stdout);
  
  return 0;
}
#endif

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:222:5: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  222 |     if (v == T) return dist[v];
      |     ^~

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