oj.uz

답안 #413801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413801 2021-05-29T13:54:55 Z flashmt 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1359 ms 55896 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int LG = 18;

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 (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 12 ms 28488 KB Output is correct
2 Correct 13 ms 28436 KB Output is correct
3 Correct 239 ms 50272 KB Output is correct
4 Correct 1184 ms 55804 KB Output is correct
5 Correct 904 ms 42184 KB Output is correct
6 Correct 1283 ms 55896 KB Output is correct
7 Correct 815 ms 47228 KB Output is correct
8 Correct 1359 ms 55800 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 28488 KB Output is correct
2 Correct 13 ms 28436 KB Output is correct
3 Correct 239 ms 50272 KB Output is correct
4 Correct 1184 ms 55804 KB Output is correct
5 Correct 904 ms 42184 KB Output is correct
6 Correct 1283 ms 55896 KB Output is correct
7 Correct 815 ms 47228 KB Output is correct
8 Correct 1359 ms 55800 KB Output is correct
9 Correct 14 ms 28488 KB Output is correct
10 Correct 12 ms 28488 KB Output is correct
11 Correct 13 ms 28488 KB Output is correct
12 Correct 13 ms 28408 KB Output is correct
13 Incorrect 16 ms 28488 KB Output isn't correct
14 Halted 0 ms 0 KB -