oj.uz

Submission #899887

# Submission time Handle Problem Language Result Execution time Memory
899887 2024-01-07T08:19:27 Z rxlfd314 Sky Walking (IOI19_walk) C++17
0 / 100
 3247 ms 1048576 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

constexpr ll LL_INF = 0x3f3f3f3f3f3f3f3f;

ll ST12(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G, int LEN) {
  const int N = size(X), M = size(L);
  vt<ari3> points;
  FOR(i, 0, M-1)
    FOR(j, L[i], R[i])
      points.push_back({j, Y[i], i});
  FOR(i, 0, N-1)
    points.push_back({i, 0, -1});
  
  sort(all(points));
  points.erase(unique(all(points)), end(points));
  
  vt<int> prv(M, -1);
  
  vt<vt<ari2>> adj(size(points));
  priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
  vt<ll> dst(size(points), LL_INF);
  FOR(i, 0, size(points)-1) {
    if (i && points[i][0] == points[i-1][0] && points[i][1] <= H[points[i][0]]) {
      adj[i-1].push_back({i, points[i][1] - points[i-1][1]});
      adj[i].push_back({i-1, points[i][1] - points[i-1][1]});
    }
    if (~points[i][2] && ~prv[points[i][2]]) {
      adj[i].push_back({prv[points[i][2]], X[points[i][0]] - X[points[prv[points[i][2]]][0]]});
      adj[prv[points[i][2]]].push_back({i, X[points[i][0]] - X[points[prv[points[i][2]]][0]]});
    }
    if (~points[i][2])
      prv[points[i][2]] = i;
    if (points[i][0] == S && !points[i][1])
      pq.push({dst[i] = 0, i});
  }
  
  while (size(pq)) {
    auto [d, i] = pq.top();
    pq.pop();
    if (points[i][0] == G && !points[i][1])
      return d;
    if (d > dst[i])
      continue;
    #ifdef DEBUG
    cout << "at " << X[points[i][0]] << ' ' << points[i][1] << " with dist of " << d << '\n';
    #endif
    for (auto &[j, v] : adj[i])
      if (d + v < dst[j])
        pq.push({dst[j] = d + v, j});
  }
  
  return -1;
}


struct ST {
  ll val;
  ST *lft, *rht;
  ST() : val(LL_INF), lft(nullptr), rht(nullptr) {}
  void upd(int p, ll v, int tl, int tr) {
    if (tl == tr) {
      val = v;
      return;
    }
    int tm = tl + tr >> 1;
    if (p <= tm) {
      if (!lft)
        lft = new ST();
      lft->upd(p, v, tl, tm);
    } else {
      if (!rht)
        rht = new ST();
      rht->upd(p, v, tm+1, tr);
    }
    val = min(lft ? lft->val : LL_INF, rht ? rht->val : LL_INF);
  }
  ll qry(int ql, int qr, int tl, int tr) {
    if (tl > qr || tr < ql)
      return LL_INF;
    if (ql <= tl && tr <= qr)
      return val;
    int tm = tl + tr >> 1;
    return min(lft ? lft->qry(ql, qr, tl, tm) : LL_INF, rht ? rht->qry(ql, qr, tm+1, tr) : LL_INF);
  }
};

ll ST34(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G) {
  const int N = size(X), M = size(L);
  vt<int> ins[N], rem[N];
  FOR(i, 0, M-1) {
    ins[L[i]].push_back(i);
    rem[R[i]].push_back(i);
  }
  ST *st_up = new ST(); // query from up
  ST *st_down = new ST(); // query from down
  st_down->upd(0, 0, 0, 1e9);
  FOR(i, 0, N-2) {
    #ifdef DEBUG
    cout << "currently at " << i << '\n';
    #endif
    vt<arl2> upd;
    for (int j : ins[i]) {
      ll d = st_down->qry(0, Y[j], 0, 1e9);
      ll u = st_up->qry(Y[j], H[i], 0, 1e9);
      #ifdef DEBUG
      cout << Y[j] << ": " << d + X[i] + Y[j] << ' ' << u + X[i] - Y[j] << '\n';
      #endif
      upd.push_back({min(d < LL_INF ? d + X[i] + Y[j] : LL_INF, u < LL_INF ? u + X[i] - Y[j] : LL_INF), j});
    }
    for (int j : rem[i]) {
      st_down->upd(Y[j], LL_INF, 0, 1e9);
      st_up->upd(Y[j], LL_INF, 0, 1e9);
    }
    for (auto [a, j] : upd) {
      st_down->upd(Y[j], a < LL_INF ? a - X[i] - Y[j] : LL_INF, 0, 1e9);
      st_up->upd(Y[j], a < LL_INF ? a - X[i] + Y[j] : LL_INF, 0, 1e9);
    }
    st_down->upd(0, LL_INF, 0, 1e9);
  }
  ll ans = st_up->qry(0, H[N-1], 0, 1e9);
  return ans < LL_INF ? ans + X[N-1] : -1ll;
}

ll min_distance(vt<int> X, vt<int> H, vt<int> L, vt<int> R, vt<int> Y, int S, int G) {
	const int N = size(X), M = size(L);
  if (!S && G == N-1)
    return ST34(X, H, L, R, Y, S, G);
  bool sub2 = true;
  int LEN = N;
  FOR(i, 0, M-1) {
    sub2 &= R[i] - L[i] < 15;
    LEN += R[i] - L[i] + 1;
  }
  if (sub2 || N < 51 && M < 51)
    return ST12(X, H, L, R, Y, S, G, LEN);
}

Compilation message

walk.cpp: In member function 'void ST::upd(int, ll, int, int)':
walk.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
walk.cpp: In member function 'll ST::qry(int, int, int, int)':
walk.cpp:97:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
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:149:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  149 |   if (sub2 || N < 51 && M < 51)
      |               ~~~~~~~^~~~~~~~~
walk.cpp:151:1: warning: control reaches end of non-void function [-Wreturn-type]
  151 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 1 ms 364 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 231 ms 76944 KB Output is correct
4 Correct 354 ms 84620 KB Output is correct
5 Runtime error 3247 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 4580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 4580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 1 ms 364 KB Output isn't correct
17 Halted 0 ms 0 KB -