oj.uz

Submission #716155

# Submission time Handle Problem Language Result Execution time Memory
716155 2023-03-29T06:33:27 Z schiftyfive4 Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1561 ms 98724 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) "MJ >> LAMELO"
#endif

template <typename T, class F = function<T(const T&, const T&)>>
struct sparse_table {
  int n;
  vector<vector<T>> mat;
  F func;
  sparse_table() {}
  sparse_table(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  T get(int L, int R) const {
    assert(0 <= L && L <= R && R <= n - 1);
    int lg = 32 - __builtin_clz(R - L + 1) - 1;
    return func(mat[lg][L], mat[lg][R - (1 << lg) + 1]);
  }
};

const int lg = 20;
vector<int> h;
vector<vector<int>> g;
vector<vector<int>> go_low;
vector<vector<int>> go_high;
vector<vector<int>> go_right;
sparse_table<int> st;
int n;

void init(int N, vector<int> H) {
  n = N;
  h = H;
  h.push_back(1e9);
  g.resize(n + 1);
  vector<int> t;
  for (int i = 0; i < n; i++) {
    while (!t.empty() && h[i] > h[t.back()]) {
      t.pop_back();
    }
    if (!t.empty()) {
      g[i].push_back(t.back());
    }
    t.push_back(i);
  }
  go_right = vector<vector<int>>(n + 1, vector<int>(lg));
  t.clear();
  for (int i = n - 1; i >= 0; i--) {
    go_right[i][0] = i;
    while (!t.empty() && h[i] > h[t.back()]) {
      t.pop_back();
    }
    if (!t.empty()) {
      g[i].push_back(t.back());
      go_right[i][0] = t.back();
    }
    t.push_back(i);
  }
  for (int i = 0; i < n; i++) {
    if (g[i].size() == 2 && h[g[i][0]] > h[g[i][1]]) {
      swap(g[i][0], g[i][1]);
    }
  }
  go_low = vector<vector<int>>(n + 1, vector<int>(lg));
  go_high = vector<vector<int>>(n + 1, vector<int>(lg));
  for (int i = 0; i <= n; i++) {
    go_low[i][0] = go_high[i][0] = n;
    if (g[i].size() > 0) {
      go_low[i][0] = g[i][0];
    }
    if (g[i].size() > 1){
      go_high[i][0] = g[i][1];
    }
  }
  for (int b = 1; b < lg; b++) {
    for (int i = 0; i <= n; i++) {
      go_low[i][b] = go_low[go_low[i][b - 1]][b - 1];
      go_high[i][b] = go_high[go_high[i][b - 1]][b - 1];
      go_right[i][b] = go_right[go_right[i][b - 1]][b - 1];
    }
  }
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  st = sparse_table<int>(p, [&](int i, int j) { return h[i] > h[j] ? i : j; });
}

int minimum_jumps(int a, int b, int c, int d) {
  int x = st.get(c, d);
  if (h[st.get(b, c - 1)] > h[x]) {
    return -1;
  }
  int l = a;
  int r = b;
  while (l < r) {
    int mid = (l + r) >> 1;
    int pos = st.get(mid, b);
    if (h[pos] > h[x]) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  int s = st.get(l, b);
  l = c;
  r = d;
  while (l < r) {
    int mid = (l + r) >> 1;
    int pos = st.get(c, mid);
    if (h[pos] > h[s]) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  int t = l;
  int ans = 0;
  for (int b = lg - 1; b >= 0; b--) {
    int ns = go_high[s][b];
    if (h[ns] < h[t]) {
      s = ns;
      ans += (1 << b);
    }
  }
  assert(s < c);
  if ((c <= go_low[s][0] && go_low[s][0] <= d) || (c <= go_high[s][0] && go_high[s][0] <= d)) {
    return ans + 1;
  }
  if (h[go_high[s][0]] < h[x]) {
    return ans + 2;
  }
  assert(h[go_high[s][0]] > h[x]);
  assert(s < c);
  for (int b = lg - 1; b >= 0; b--) {
    int ns = go_low[s][b];
    if (ns < c) {
      s = ns;
      ans += (1 << b);
    }
  }
  return ans + 1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 304 ms 78372 KB Output is correct
4 Correct 1346 ms 98664 KB Output is correct
5 Correct 1153 ms 49400 KB Output is correct
6 Correct 1561 ms 98668 KB Output is correct
7 Correct 1085 ms 67112 KB Output is correct
8 Correct 1307 ms 98576 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 220 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 2 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 220 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 2 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 188 ms 78528 KB Output is correct
6 Correct 212 ms 97876 KB Output is correct
7 Correct 107 ms 49832 KB Output is correct
8 Correct 206 ms 97896 KB Output is correct
9 Correct 31 ms 14672 KB Output is correct
10 Correct 204 ms 97884 KB Output is correct
11 Correct 203 ms 98692 KB Output is correct
12 Correct 216 ms 98356 KB Output is correct
13 Correct 194 ms 98432 KB Output is correct
14 Correct 223 ms 97884 KB Output is correct
15 Correct 254 ms 98272 KB Output is correct
16 Correct 236 ms 98608 KB Output is correct
17 Correct 234 ms 98724 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Incorrect 1 ms 336 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 327 ms 44440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 327 ms 44440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 304 ms 78372 KB Output is correct
4 Correct 1346 ms 98664 KB Output is correct
5 Correct 1153 ms 49400 KB Output is correct
6 Correct 1561 ms 98668 KB Output is correct
7 Correct 1085 ms 67112 KB Output is correct
8 Correct 1307 ms 98576 KB Output is correct
9 Correct 0 ms 220 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 2 ms 208 KB Output isn't correct
14 Halted 0 ms 0 KB -