제출 #711631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711631		irmuun	밀림 점프 (APIO21_jumps)	C++17	4 / 100	1020 ms	14460 KiB

jumps

#include<bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define PI 3.1415926535897932384626433
#define all(s) s.begin(),s.end() 

const int maxn=200000,INF=1e9;
bool ok=true;
vector<int>adj[maxn+5];
int n,dist[maxn+5];

int dfs(int a,int b,int c,int d){
    queue<int>q;
    fill(dist,dist+n+1,INF);
    for(int i=a;i<=b;i++) q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(c<=x&&x<=d) return dist[x];
        for(auto u:adj[x]){
            if(dist[u]==INF){
                dist[u]=dist[x]+1;
                q.push(u);
            }
        }
    }
    return -1;
}
void init(int N,vector<int>H){
    n=N;
    for(int i=0;i<n;i++){
        if(H[i]!=i+1) ok=false;
    }
    stack<pair<int,int>>s;
    for(int i=0;i<n;i++){
        while(!s.empty()&&s.top().ff<H[i]) s.pop();
        if(!s.empty()) adj[i].pb(s.top().ss);
        s.push({H[i],i});
    }
    while(!s.empty()) s.pop();
    for(int i=n-1;i>=0;i--){
        while(!s.empty()&&s.top().ff<H[i]) s.pop();
        if(!s.empty()) adj[i].pb(s.top().ss);
        s.push({H[i],i});
    }
}
int minimum_jumps(int A, int B, int C, int D){
    if(ok==true){
        return C-B;
    }
    return dfs(A,B,C,D);
}

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