제출 #980665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
980665		vjudge1	밀림 점프 (APIO21_jumps)	C++17	33 / 100	4086 ms	13980 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#define sz size()
#define ll int
using namespace std;
const ll INF = 1e9;
int n;
vector<vector<ll>> v;

void init(int N, vector<int> h)
{
    n = N;
    v.resize(n);
    vector<ll> q;
    for(ll i = 0; i < n; ++i)
    {
        while(q.sz && h[q.back()] < h[i])
            v[q.back()].push_back(i),
            q.pop_back();
        q.push_back(i);
    }
    q.clear();
    for(ll i = n - 1; i >= 0; --i)
    {
        while(q.sz && h[q.back()] < h[i])
            v[q.back()].push_back(i),
            q.pop_back();
        q.push_back(i);
    }
}

int minimum_jumps(int a, int b, int c, int d)
{
        vector<ll> dist(n, INF);
        queue<ll> q;
        for(ll i = a; i <= b; ++i)
        {
            dist[i] = 0;
            q.push(i);
        }
        while(q.sz)
        {
            ll s = q.front();
            q.pop();
            for(ll t : v[s])
            {
                if(dist[t] < INF) continue;
                dist[t] = dist[s] + 1;
                q.push(t);
            }
        }
        ll ans = INF;
        for(ll i = c; i <= d; ++i)
            ans = min(ans, dist[i]);
        return ans < INF ? ans : -1;
}

//signed main()
//{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
//}

• Subtask 1: 0 / 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