oj.uz

Submission #413901

# Submission time Handle Problem Language Result Execution time Memory
413901 2021-05-29T16:54:08 Z flashmt Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1419 ms 55900 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int LG = 18;

int n, l[N][LG], r[N][LG], high[N][LG];
vector<int> h;

void initEdges()
{
  vector<pair<int, int>> sortedH;
  for (int i = 0; i < n; i++)
    sortedH.push_back({h[i], i});
  sort(sortedH.begin(), sortedH.end(), greater<pair<int, int>>());
  set<int> s;
  s.insert(-1);
  s.insert(n);
  memset(l, -1, sizeof l);
  memset(r, -1, sizeof r);
  memset(high, -1, sizeof high);
  for (auto [_, i] : sortedH)
  {
    auto it = s.lower_bound(i);
    r[i][0] = *it;
    l[i][0] = *(--it);
    if (l[i][0] < 0) high[i][0] = r[i][0];
    else if (r[i][0] < 0) high[i][0] = l[i][0];
    else if (h[l[i][0]] > h[r[i][0]]) high[i][0] = l[i][0];
    else high[i][0] = r[i][0];
    s.insert(i);
  }
}

void constructTable()
{
  for (int j = 0; j + 1 < LG; j++)
    for (int i = 0; i < n; i++)
    {
      if (l[i][j] >= 0 && l[i][j] < n)
        l[i][j + 1] = l[l[i][j]][j];
      if (r[i][j] >= 0 && r[i][j] < n)
        r[i][j + 1] = r[r[i][j]][j];
      if (high[i][j] >= 0 && high[i][j] < n)
        high[i][j + 1] = high[high[i][j]][j];
    }
}

void init(int N, vector<int> H) {
  n = N;
  h = H;
  h[n] = 0;
  initEdges();
  constructTable();
}

int jump(int &s, int table[N][LG], function<int(int)> cond)
{
  int res = 0;
  for (int i = LG - 1; i >= 0; i--)
  {
    int x = table[s][i];
    if (x >= 0 && x < n && cond(x))
    {
      s = x;
      res |= 1 << i;
    }
  }
  return res;
}

int minimum_jumps(int A, int B, int C, int D) {
  int s = B;
  // find where to start
  jump(s, l, [&](int x) {
    return x >= A && r[x][0] >= 0 && r[x][0] <= D;
  });
  // use high edges as most as possible
  int ans = jump(s, high, [&](int x) {
    return r[x][0] >= 0 && r[x][0] < C;
  });
  ans += jump(s, r, [&](int x) {
    return x < C;
  });
  return r[s][0] >= C && r[s][0] <= D ? ans + 1 : -1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42560 KB Output is correct
2 Correct 22 ms 42560 KB Output is correct
3 Correct 343 ms 53192 KB Output is correct
4 Correct 1267 ms 55856 KB Output is correct
5 Correct 1121 ms 49296 KB Output is correct
6 Correct 1309 ms 55856 KB Output is correct
7 Correct 1184 ms 51708 KB Output is correct
8 Correct 1419 ms 55820 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42548 KB Output is correct
2 Correct 20 ms 42568 KB Output is correct
3 Correct 21 ms 42568 KB Output is correct
4 Correct 21 ms 42600 KB Output is correct
5 Correct 25 ms 42488 KB Output is correct
6 Incorrect 24 ms 42532 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42548 KB Output is correct
2 Correct 20 ms 42568 KB Output is correct
3 Correct 21 ms 42568 KB Output is correct
4 Correct 21 ms 42600 KB Output is correct
5 Correct 25 ms 42488 KB Output is correct
6 Incorrect 24 ms 42532 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42568 KB Output is correct
2 Correct 23 ms 42568 KB Output is correct
3 Correct 23 ms 42692 KB Output is correct
4 Correct 23 ms 42464 KB Output is correct
5 Correct 218 ms 53320 KB Output is correct
6 Correct 283 ms 55900 KB Output is correct
7 Correct 133 ms 49316 KB Output is correct
8 Correct 282 ms 55856 KB Output is correct
9 Runtime error 7 ms 1096 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42560 KB Output is correct
2 Correct 21 ms 42568 KB Output is correct
3 Correct 22 ms 42480 KB Output is correct
4 Incorrect 419 ms 48644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42560 KB Output is correct
2 Correct 21 ms 42568 KB Output is correct
3 Correct 22 ms 42480 KB Output is correct
4 Incorrect 419 ms 48644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42560 KB Output is correct
2 Correct 22 ms 42560 KB Output is correct
3 Correct 343 ms 53192 KB Output is correct
4 Correct 1267 ms 55856 KB Output is correct
5 Correct 1121 ms 49296 KB Output is correct
6 Correct 1309 ms 55856 KB Output is correct
7 Correct 1184 ms 51708 KB Output is correct
8 Correct 1419 ms 55820 KB Output is correct
9 Correct 21 ms 42548 KB Output is correct
10 Correct 20 ms 42568 KB Output is correct
11 Correct 21 ms 42568 KB Output is correct
12 Correct 21 ms 42600 KB Output is correct
13 Correct 25 ms 42488 KB Output is correct
14 Incorrect 24 ms 42532 KB Output isn't correct
15 Halted 0 ms 0 KB -