제출 #1051980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1051980		kachim2	밀림 점프 (APIO21_jumps)	C++17	37 / 100	4080 ms	6628 KiB

jumps

#include "jumps.h"
#include<queue>
#include <vector>
#include <iostream>
using namespace std;
std::vector<int> H;
vector<int> nxt;
vector<int> prv;
bool subtask1=1;
void init(int N, std::vector<int> nH)
{
  for(int i = 0; i < N; i++){
    if(nH[i]!=i+1) subtask1=0;
  }
  H = nH;
  nxt.resize(N);
  prv.resize(N);
  {
  vector<int> kmon;
  for (int i = 0; i < N; i++)
  {
    if (kmon.empty())
    {
      kmon.push_back(i);
      prv[i] = -1;
      continue;
    }
    while (H[kmon.back()] < H[i])
    {
      kmon.pop_back();
      if (kmon.empty())
      {
        kmon.push_back(i);
        prv[i] = -1;
        goto nd;
      }
    }
    prv[i] = kmon.back();
    kmon.push_back(i);
    nd:;
  }
  }
  {
  vector<int> kmon;
  for (int i = N-1; i>=0; i--)
  {
    if (kmon.empty())
    {
      kmon.push_back(i);
      nxt[i] = -1;
      continue;
    }
    while (H[kmon.back()] < H[i])
    {
      kmon.pop_back();
      if (kmon.empty())
      {
        kmon.push_back(i);
        nxt[i] = -1;
        goto nd2;
      }
    }
    nxt[i] = kmon.back();
    kmon.push_back(i);
    nd2:;
  }
  }
}

int minimum_jumps(int A, int B, int C, int D)
{
  if (subtask1) return C-B;
  int mcd = 0;
  for (int i = C; i <= D; i++)
  {
    mcd = max(mcd, H[i]);
  }
  int bs = 0;
  for (int i = B; i >= A; i--)
  {
    // cerr << H[i] << ' ';
    if (H[i] < mcd)
      bs = max(bs, i);
    else
      break;
  }
  // cerr << bs << '\n';

  vector<bool> visited(H.size(), 0);

  queue<pair<int, int>> q;
  for(int i = A; i <=B; i++)
  q.push({i, 0});
  while(!q.empty()){
    auto x = q.front();
    q.pop();
    if(visited[x.first]) continue;
    visited[x.first] = 1;
    if(x.first >= C && x.first <= D) return x.second;
    if(nxt[x.first]!=-1) q.push({nxt[x.first], x.second+1});
    if(prv[x.first]!=-1) q.push({prv[x.first], x.second+1});
  }
  return -1;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19