oj.uz

Submission #418653

# Submission time Handle Problem Language Result Execution time Memory
418653 2021-06-05T16:46:31 Z usachevd0 Sky Walking (IOI19_walk) C++17
0 / 100
 1330 ms 188664 KB 
#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 int 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;
    int 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

walk.cpp:55:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   55 | const int INF64 = 1e18;
      |                   ^~~~
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 104004 KB Output is correct
2 Correct 71 ms 104024 KB Output is correct
3 Correct 63 ms 104144 KB Output is correct
4 Correct 65 ms 104044 KB Output is correct
5 Correct 63 ms 104100 KB Output is correct
6 Correct 62 ms 104124 KB Output is correct
7 Correct 63 ms 104132 KB Output is correct
8 Correct 63 ms 104120 KB Output is correct
9 Correct 63 ms 104260 KB Output is correct
10 Correct 63 ms 104124 KB Output is correct
11 Correct 65 ms 104112 KB Output is correct
12 Correct 63 ms 104128 KB Output is correct
13 Correct 62 ms 104048 KB Output is correct
14 Correct 62 ms 104132 KB Output is correct
15 Correct 62 ms 104124 KB Output is correct
16 Incorrect 64 ms 104144 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104060 KB Output is correct
2 Correct 64 ms 104144 KB Output is correct
3 Correct 665 ms 165740 KB Output is correct
4 Incorrect 640 ms 177644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 120500 KB Output is correct
2 Correct 1098 ms 174600 KB Output is correct
3 Correct 1132 ms 176872 KB Output is correct
4 Correct 1132 ms 185976 KB Output is correct
5 Incorrect 1330 ms 188664 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 120500 KB Output is correct
2 Correct 1098 ms 174600 KB Output is correct
3 Correct 1132 ms 176872 KB Output is correct
4 Correct 1132 ms 185976 KB Output is correct
5 Incorrect 1330 ms 188664 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 104004 KB Output is correct
2 Correct 71 ms 104024 KB Output is correct
3 Correct 63 ms 104144 KB Output is correct
4 Correct 65 ms 104044 KB Output is correct
5 Correct 63 ms 104100 KB Output is correct
6 Correct 62 ms 104124 KB Output is correct
7 Correct 63 ms 104132 KB Output is correct
8 Correct 63 ms 104120 KB Output is correct
9 Correct 63 ms 104260 KB Output is correct
10 Correct 63 ms 104124 KB Output is correct
11 Correct 65 ms 104112 KB Output is correct
12 Correct 63 ms 104128 KB Output is correct
13 Correct 62 ms 104048 KB Output is correct
14 Correct 62 ms 104132 KB Output is correct
15 Correct 62 ms 104124 KB Output is correct
16 Incorrect 64 ms 104144 KB Output isn't correct
17 Halted 0 ms 0 KB -