oj.uz

Submission #716149

# Submission time Handle Problem Language Result Execution time Memory
716149 2023-03-29T06:24:31 Z schiftyfive4 Rainforest Jumps (APIO21_jumps) C++14
60 / 100
 1394 ms 98808 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_right[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 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 259 ms 78368 KB Output is correct
4 Correct 1116 ms 98612 KB Output is correct
5 Correct 1046 ms 49348 KB Output is correct
6 Correct 1330 ms 98676 KB Output is correct
7 Correct 830 ms 67128 KB Output is correct
8 Correct 1394 ms 98808 KB Output is correct

Subtask #2
0 / 8.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 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Incorrect 3 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Correct 0 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Incorrect 3 ms 336 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.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 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 169 ms 78560 KB Output is correct
6 Correct 202 ms 97792 KB Output is correct
7 Correct 108 ms 49856 KB Output is correct
8 Correct 202 ms 97836 KB Output is correct
9 Correct 30 ms 14596 KB Output is correct
10 Correct 216 ms 97840 KB Output is correct
11 Correct 192 ms 98620 KB Output is correct
12 Correct 217 ms 98456 KB Output is correct
13 Correct 192 ms 98456 KB Output is correct
14 Correct 203 ms 97892 KB Output is correct
15 Correct 251 ms 98192 KB Output is correct
16 Correct 210 ms 98620 KB Output is correct
17 Correct 211 ms 98716 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 720 KB Output is correct
27 Correct 2 ms 1104 KB Output is correct
28 Correct 2 ms 1104 KB Output is correct
29 Correct 2 ms 1104 KB Output is correct
30 Correct 2 ms 1104 KB Output is correct
31 Correct 2 ms 1232 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 203 ms 97680 KB Output is correct
34 Correct 201 ms 97868 KB Output is correct
35 Correct 194 ms 98460 KB Output is correct
36 Correct 203 ms 97884 KB Output is correct
37 Correct 237 ms 98284 KB Output is correct
38 Correct 190 ms 98724 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 117 ms 56368 KB Output is correct
41 Correct 210 ms 97876 KB Output is correct
42 Correct 218 ms 98500 KB Output is correct
43 Correct 217 ms 97876 KB Output is correct
44 Correct 243 ms 98304 KB Output is correct
45 Correct 191 ms 98568 KB Output is correct

Subtask #5
23.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 Correct 281 ms 44436 KB Output is correct
5 Correct 910 ms 97892 KB Output is correct
6 Correct 670 ms 16076 KB Output is correct
7 Correct 1192 ms 97808 KB Output is correct
8 Correct 548 ms 33464 KB Output is correct
9 Correct 1128 ms 97808 KB Output is correct
10 Correct 1290 ms 98668 KB Output is correct
11 Correct 961 ms 98612 KB Output is correct
12 Correct 1082 ms 98556 KB Output is correct
13 Correct 1077 ms 97904 KB Output is correct
14 Correct 1158 ms 98268 KB Output is correct
15 Correct 942 ms 98664 KB Output is correct
16 Correct 927 ms 98576 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 3 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 592 KB Output is correct
27 Correct 22 ms 1208 KB Output is correct
28 Correct 19 ms 1232 KB Output is correct
29 Correct 20 ms 1104 KB Output is correct
30 Correct 16 ms 1104 KB Output is correct
31 Correct 17 ms 1232 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 117 ms 56336 KB Output is correct
34 Correct 201 ms 97796 KB Output is correct
35 Correct 195 ms 98520 KB Output is correct
36 Correct 221 ms 97800 KB Output is correct
37 Correct 272 ms 98192 KB Output is correct
38 Correct 195 ms 98616 KB Output is correct

Subtask #6
21.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 Correct 281 ms 44436 KB Output is correct
5 Correct 910 ms 97892 KB Output is correct
6 Correct 670 ms 16076 KB Output is correct
7 Correct 1192 ms 97808 KB Output is correct
8 Correct 548 ms 33464 KB Output is correct
9 Correct 1128 ms 97808 KB Output is correct
10 Correct 1290 ms 98668 KB Output is correct
11 Correct 961 ms 98612 KB Output is correct
12 Correct 1082 ms 98556 KB Output is correct
13 Correct 1077 ms 97904 KB Output is correct
14 Correct 1158 ms 98268 KB Output is correct
15 Correct 942 ms 98664 KB Output is correct
16 Correct 927 ms 98576 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 3 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 592 KB Output is correct
27 Correct 22 ms 1208 KB Output is correct
28 Correct 19 ms 1232 KB Output is correct
29 Correct 20 ms 1104 KB Output is correct
30 Correct 16 ms 1104 KB Output is correct
31 Correct 17 ms 1232 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 117 ms 56336 KB Output is correct
34 Correct 201 ms 97796 KB Output is correct
35 Correct 195 ms 98520 KB Output is correct
36 Correct 221 ms 97800 KB Output is correct
37 Correct 272 ms 98192 KB Output is correct
38 Correct 195 ms 98616 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 0 ms 208 KB Output is correct
41 Correct 0 ms 208 KB Output is correct
42 Correct 248 ms 44464 KB Output is correct
43 Correct 865 ms 97828 KB Output is correct
44 Correct 660 ms 15940 KB Output is correct
45 Correct 1008 ms 97804 KB Output is correct
46 Correct 444 ms 33464 KB Output is correct
47 Correct 970 ms 97848 KB Output is correct
48 Correct 1248 ms 98676 KB Output is correct
49 Correct 1240 ms 98708 KB Output is correct
50 Correct 998 ms 98488 KB Output is correct
51 Correct 1081 ms 97804 KB Output is correct
52 Correct 1310 ms 98360 KB Output is correct
53 Correct 1030 ms 98572 KB Output is correct
54 Correct 1062 ms 98716 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Correct 252 ms 97492 KB Output is correct
57 Correct 1061 ms 97968 KB Output is correct
58 Correct 488 ms 17040 KB Output is correct
59 Correct 966 ms 97976 KB Output is correct
60 Correct 465 ms 34452 KB Output is correct
61 Correct 1069 ms 97788 KB Output is correct
62 Correct 1073 ms 98668 KB Output is correct
63 Correct 1173 ms 98572 KB Output is correct
64 Correct 1277 ms 98376 KB Output is correct
65 Correct 1014 ms 97952 KB Output is correct
66 Correct 1380 ms 98236 KB Output is correct
67 Correct 1092 ms 98676 KB Output is correct
68 Correct 1025 ms 98664 KB Output is correct
69 Correct 0 ms 208 KB Output is correct
70 Correct 1 ms 208 KB Output is correct
71 Correct 2 ms 336 KB Output is correct
72 Correct 1 ms 336 KB Output is correct
73 Correct 2 ms 336 KB Output is correct
74 Correct 2 ms 336 KB Output is correct
75 Correct 2 ms 336 KB Output is correct
76 Correct 0 ms 208 KB Output is correct
77 Correct 0 ms 208 KB Output is correct
78 Correct 2 ms 208 KB Output is correct
79 Correct 2 ms 336 KB Output is correct
80 Correct 2 ms 336 KB Output is correct
81 Correct 2 ms 336 KB Output is correct
82 Correct 2 ms 336 KB Output is correct
83 Correct 2 ms 336 KB Output is correct
84 Correct 1 ms 336 KB Output is correct
85 Correct 4 ms 336 KB Output is correct
86 Correct 9 ms 1104 KB Output is correct
87 Correct 17 ms 1232 KB Output is correct
88 Correct 21 ms 1208 KB Output is correct
89 Correct 19 ms 1212 KB Output is correct
90 Correct 17 ms 1232 KB Output is correct
91 Correct 0 ms 336 KB Output is correct
92 Correct 1 ms 592 KB Output is correct
93 Correct 17 ms 1204 KB Output is correct
94 Correct 21 ms 1212 KB Output is correct
95 Correct 11 ms 1220 KB Output is correct
96 Correct 20 ms 1104 KB Output is correct
97 Correct 18 ms 1104 KB Output is correct
98 Correct 0 ms 208 KB Output is correct
99 Correct 216 ms 97692 KB Output is correct
100 Correct 203 ms 97804 KB Output is correct
101 Correct 192 ms 98432 KB Output is correct
102 Correct 199 ms 97800 KB Output is correct
103 Correct 242 ms 98280 KB Output is correct
104 Correct 190 ms 98588 KB Output is correct
105 Correct 0 ms 208 KB Output is correct
106 Correct 122 ms 56320 KB Output is correct
107 Correct 211 ms 97992 KB Output is correct
108 Correct 191 ms 98488 KB Output is correct
109 Correct 203 ms 97824 KB Output is correct
110 Correct 235 ms 98192 KB Output is correct
111 Correct 199 ms 98676 KB Output is correct

Subtask #7
0 / 19.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 259 ms 78368 KB Output is correct
4 Correct 1116 ms 98612 KB Output is correct
5 Correct 1046 ms 49348 KB Output is correct
6 Correct 1330 ms 98676 KB Output is correct
7 Correct 830 ms 67128 KB Output is correct
8 Correct 1394 ms 98808 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 2 ms 208 KB Output is correct
14 Incorrect 3 ms 336 KB Output isn't correct
15 Halted 0 ms 0 KB -