제출 #545424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545424		fadi57	밀림 점프 (APIO21_jumps)	C++14	23 / 100	1130 ms	36552 KiB

jumps

#include<bits/stdc++.h>
//#include "jumps.h"
using namespace std;
const int mx=3e5+10;
typedef long long ll;
const ll mod=998244353 ;
const int SQ=400;
const ll inf=1e8+10;
int n;
int dp[20][mx],dp2[20][mx],lft[mx],right1[mx];vector<int>h;
void pre(){
   for(int i=0;i<20;i++){

      for(int j=0;j<n;j++){
            if(i==0){
        dp2[i][j]=right1[j];
                }else{
                    if(dp2[i-1][j]==-1){
                        dp2[i][j]=-1;
                    }else{
                         dp2[i][j]=dp2[i-1][dp2[i-1][j]];
                    }



        }

      }

   }

for(int i=0;i<20;i++){

      for(int j=0;j<n;j++){
            if(i==0){
                    if(h[lft[j]]>h[right1[j]]){
                        dp[i][j]=lft[j];
                    }else{
                       dp[i][j]=right1[j];
                    }

                }else{
                    if(dp[i-1][j]!=-1){
                         dp[i][j]=dp[i-1][dp[i-1][j]];
                    }else{

                    dp[i][j]=-1;
                    }



        }

      }

   }


  }

  void init(int N, vector<int>H) {
      h=H;
          n=N;
          lft[0]=-1;
          stack<int>s;
          s.push(0);

          for(int i=1;i<n;i++){
               while(!s.empty()&&h[s.top()]<h[i]){
                   s.pop();
               }
               if(s.empty()){
              lft[i]=-1;
               }else{
                 lft[i]=s.top();

               }
               s.push(i);

          }
         right1[n-1]=-1;
       while(!s.empty()){
                   s.pop();
               }
        s.push(n-1);
        for(int i=n-2;i>=0;i--){
             while(!s.empty()&&h[s.top()]<h[i]){
                   s.pop();
               }
               if(s.empty()){
              right1[i]=-1;
               }else{
                 right1[i]=s.top();

               }
               s.push(i);
        }

  pre();
  }

int minimum_jumps(int A, int B, int C, int D) {
    int a=A;int ans=0;int ans2=0;
    for(int j=19;j>=0;j--){
        if(dp2[j][a]!=-1&&h[dp2[j][a]]<=h[C]){
       //  cout<<j<<" "<<a<<endl;
            a=dp2[j][a];
            ans2+=(1<<j);
            }

    }
    if(a!=C){return -1;}
    a=A;
  //  cout<<a<<" "<<endl;
     for(int j=19;j>=0;j--){
            if(a==C){break;}
        if(dp[j][a]!=-1&&h[dp[j][a]]<=h[C]){
        // cout<<j<<" "<<a<<endl;
            a=dp[j][a];
            ans+=(1<<j);
            }

    }
    if(a!=C){
          for(int j=19;j>=0;j--){
                if(a==C){break;}
        if(dp2[j][a]!=-1&&h[dp2[j][a]]<=h[C]){
        // cout<<j<<" "<<a<<endl;
            a=dp2[j][a];
            ans+=(1<<j);
            }

    }
    }
   return ans;
 
}
/*
int main(){
    /*
       cin>>n;vector<int>v;
       for(int i=0;i<n;i++){
        int x;cin>>x;
        v.push_back(x);
       }
       init(n,v);
       pre();
       int a,b,c,d;  cin>>a>>b>>c>>d;
       cout<<dp[0][a]<<" "<<dp[1][a]<<endl;
       cout<<minimum_jumps(a,b,c,d);


  
*/

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp:140:5: warning: "/*" within comment [-Wcomment]
  140 |     /*
      |

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