제출 #824472

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

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int seg[800005], dist[200005], n;
vector<int> adj[200005];
queue<int> q;
void build(int i, int l, int r)
{
    if (l==r)
    {
        seg[i]=-1;
        return;
    }
    int mid=(l+r)/2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
    seg[i]=-1;
}
void build2(int i, int l, int r)
{
    if (l==r)
    {
        seg[i]=1e9;
        return;
    }
    int mid=(l+r)/2;
    build2(i*2, l, mid);
    build2(i*2+1, mid+1, r);
    seg[i]=1e9;
}
void upd(int i, int l, int r, int x, int y)
{
    if (l==r)
    {
        seg[i]=y;
        return;
    }
    int mid=(l+r)/2;
    if (x<=mid)
        upd(i*2, l, mid, x, y);
    else
        upd(i*2+1, mid+1, r, x, y);
    seg[i]=y;
}
void upd2(int i, int l, int r, int x, int y)
{
    if (l==r)
    {
        seg[i]=y;
        return;
    }
    int mid=(l+r)/2;
    if (x<=mid)
        upd2(i*2, l, mid, x, y);
    else
        upd2(i*2+1, mid+1, r, x, y);
    seg[i]=y;
}
int qry(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return seg[i];
    int mid=(l+r)/2, res=-1;
    if (l<=qr && ql<=mid)
        res=max(res, qry(i*2, l, mid, ql, qr));
    if (mid<qr && ql<=r)
        res=max(res, qry(i*2+1, mid+1, r, ql, qr));
    return res;
}
int qry2(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return seg[i];
    int mid=(l+r)/2, res=1e9;
    if (l<=qr && ql<=mid)
        res=min(res, qry2(i*2, l, mid, ql, qr));
    if (mid<qr && ql<=r)
        res=min(res, qry2(i*2+1, mid+1, r, ql, qr));
    return res;
}
void init(int nn, vector<int> h)
{
    n=nn;
    build(1, 1, n);
    for (int i=0; i<n; i++)
    {
        int res=(h[i]==n?-1:qry(1, 1, n, h[i]+1, n));
        if (res!=-1)
            adj[i].push_back(res);
        upd(1, 1, n, h[i], i);
    }
    build2(1, 1, n);
    for (int i=n-1; i>=0; i--)
    {
        int res=(h[i]==n?1e9:qry2(1, 1, n, h[i]+1, n));
        if (res!=1e9)
            adj[i].push_back(res);
        upd2(1, 1, n, h[i], i);
    }
}
int minimum_jumps(int a, int b, int c, int d)
{
    for (int i=0; i<n; i++)
        dist[i]=1e9;
    for (int i=a; i<=b; i++)
    {
        dist[i]=0;
        q.push(i);
    }
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int v:adj[u])
        {
            if (dist[u]+1<dist[v])
            {
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
    int ans=1e9;
    for (int i=c; i<=d; i++)
        ans=min(ans, dist[i]);
    return (ans<5e8?ans:-1);
}

• 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