oj.uz

답안 #413805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413805 2021-05-29T14:05:56 Z flashmt 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1437 ms 55852 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int LG = 18;
#define db(x) cerr << #x << " = " << x << endl

int n, l[N], r[N], toL[N][LG], toR[N][LG], maxH[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);
  for (auto [_, i] : sortedH)
  {
    auto it = s.lower_bound(i);
    r[i] = *it;
    l[i] = *(--it);
    s.insert(i);
  }
}

void constructTable()
{
  memset(toL, -1, sizeof toL);
  memset(toR, -1, sizeof toR);
  for (int i = 0; i < n; i++)
  {
    toL[i][0] = l[i];
    toR[i][0] = r[i];
    maxH[i][0] = h[i];
  }

  for (int j = 0; j + 1 < LG; j++)
    for (int i = 0; i < n; i++)
    {
      if (toL[i][j] >= 0)
        toL[i][j + 1] = toL[toL[i][j]][j];
      if (toR[i][j] >= 0)
        toR[i][j + 1] = toR[toR[i][j]][j];
      if (i + (1 << j) < n)
        maxH[i][j + 1] = max(maxH[i][j], maxH[i + (1 << j)][j]);
    }
}

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

int getMaxH(int l, int r)
{
  int bit = 31 - __builtin_clz(r - l + 1);
  return max(maxH[l][bit], maxH[r - (1 << bit) + 1][bit]);
}

int between(int x, int y, int z)
{
  return y <= x && x <= z;
}

int calcDist(int s, int from, int maxDestH)
{
  int dist = 0;
  for (int i = LG - 1; i >= 0; i--)
  {
    int x = toR[s][i];
    if (x >= 0 && x < from && h[x] < maxDestH)
    {
      dist |= 1 << i;
      s = x;
    }
  }
  return h[s] <= maxDestH ? dist + 1 : n;
}

int minimum_jumps(int A, int B, int C, int D) {
  int s = B, maxDestH = getMaxH(C, D);
  for (int i = LG - 1; i >= 0; i--)
  {
    int x = toL[s][i];
    if (x >= A && x < n && h[x] < maxDestH)
      s = x;
  }

  if (h[s] > maxDestH)
    return -1;

  if (between(l[s], C, D) || between(r[s], C, D))
    return 1;

  int ans = calcDist(s, C, maxDestH);
  if (l[s] >= 0 && l[s] < n)
    ans = min(ans, calcDist(l[s], C, maxDestH) + 1);

  return ans < n ? ans : -1;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 12 ms 28516 KB Output is correct
3 Correct 255 ms 50212 KB Output is correct
4 Correct 1437 ms 55852 KB Output is correct
5 Correct 1137 ms 42272 KB Output is correct
6 Correct 1357 ms 55788 KB Output is correct
7 Correct 905 ms 47204 KB Output is correct
8 Correct 1235 ms 55788 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 13 ms 28488 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Correct 15 ms 28424 KB Output is correct
5 Incorrect 18 ms 28464 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 13 ms 28488 KB Output is correct
3 Correct 14 ms 28472 KB Output is correct
4 Correct 15 ms 28424 KB Output is correct
5 Incorrect 18 ms 28464 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 12 ms 28488 KB Output is correct
3 Correct 12 ms 28436 KB Output is correct
4 Correct 14 ms 28572 KB Output is correct
5 Incorrect 193 ms 50448 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 12 ms 28476 KB Output is correct
3 Correct 15 ms 28392 KB Output is correct
4 Incorrect 458 ms 41032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 12 ms 28476 KB Output is correct
3 Correct 15 ms 28392 KB Output is correct
4 Incorrect 458 ms 41032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 12 ms 28516 KB Output is correct
3 Correct 255 ms 50212 KB Output is correct
4 Correct 1437 ms 55852 KB Output is correct
5 Correct 1137 ms 42272 KB Output is correct
6 Correct 1357 ms 55788 KB Output is correct
7 Correct 905 ms 47204 KB Output is correct
8 Correct 1235 ms 55788 KB Output is correct
9 Correct 13 ms 28488 KB Output is correct
10 Correct 13 ms 28488 KB Output is correct
11 Correct 14 ms 28472 KB Output is correct
12 Correct 15 ms 28424 KB Output is correct
13 Incorrect 18 ms 28464 KB Output isn't correct
14 Halted 0 ms 0 KB -