제출 #1194977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194977		dzuizz	밀림 점프 (APIO21_jumps)	C++20	100 / 100	660 ms	59956 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5,L=18;
int H[N];
int lf[N][L],rg[N][L],st[N][L],p[N][L];
int n;
void init(int _n,vector<int> _H) {
  n=_n;
  for(int i=0;i<n;++i) H[i]=_H[i];

  for(int i=0;i<n;++i) st[i][0]=i;
  for(int j=0;j<L-1;++j) for(int i=0;i+(1<<(j+1))<=n;++i){
    int a=i,b=i+(1<<j);
    if(H[st[a][j]]>H[st[b][j]]) st[i][j+1]=st[a][j];
    else st[i][j+1]=st[b][j];
  }

  stack<int> s;
  for(int i=0;i<n;++i){
    while(s.size()&&H[s.top()]<=H[i]) s.pop();
    if(s.size()) lf[i][0]=s.top();
    else lf[i][0]=i;
    s.emplace(i);
  }
  while(s.size()) s.pop();
  for(int i=n-1;i>=0;--i){
    while(s.size()&&H[s.top()]<=H[i]) s.pop();
    if(s.size()) rg[i][0]=s.top();
    else rg[i][0]=i;
    s.emplace(i);
  }
  for(int i=0;i<n;++i)
    p[i][0]=H[lf[i][0]]>H[rg[i][0]]?lf[i][0]:rg[i][0];

  for(int j=0;j<L-1;++j) for(int i=0;i<n;++i)
    p[i][j+1]=p[p[i][j]][j],
    lf[i][j+1]=lf[lf[i][j]][j],
    rg[i][j+1]=rg[rg[i][j]][j];
}

int get_min(int l,int r){
  int k=log2(r-l+1);
  return H[st[l][k]]<H[st[r-(1<<k)+1][k]]?st[l][k]:st[r-(1<<k)+1][k];
}

int minimum_jumps(int A,int B,int C,int D){
  int t=C;
  for(int j=L-1;j>=0;--j) if(rg[t][j]<=D)
    t=rg[t][j];

  int s=B;
  for(int j=L-1;j>=0;--j) if(lf[s][j]>=A&&H[lf[s][j]]<H[t])
    s=lf[s][j];

  int x=-1;
  if(B<C-1){
    x=B+1;
    for(int j=L-1;j>=0;--j) if(rg[x][j]<C)
      x=rg[x][j];
    x=H[x];
  }
  //cerr<<s<<" "<<x<<" "<<t<<'\n';
  if(H[s]>=H[t]||x>=H[t]) return -1;

  if(H[s]>=x) return 1;

  int ans=0;
  for(int j=L-1;j>=0;--j) if(H[p[s][j]]<x)
    ans+=1<<j,s=p[s][j];
  if(H[rg[s][0]]==x) return ans+2;
  else if(H[p[s][0]]<H[t]) return ans+2;

  //for(int j=0;j<L;++j) cerr<<rg[s][j]<<" "; cerr<<'\n';
  for(int j=L-1;j>=0;--j) if(rg[s][j]<C)
    ans+=1<<j,s=rg[s][j];
  //cerr<<ans<<" "<<s<<'\n';
  return ++ans;
}

int f(int i,int x,int y){
  if(x<=i&&i<=y) return 0;
  int ret=2e9;
  if(lf[i][0]!=i) ret=min(ret,f(lf[i][0],x,y)+1);
  if(rg[i][0]!=i) ret=min(ret,f(rg[i][0],x,y)+1);
  return ret;
}
int brute_force(int A,int B,int C,int D){
  int ret=2e9;
  for(int i=A;i<=B;++i)
    ret=min(ret,f(i,C,D));
  return ret==2e9?-1:ret;
}

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