제출 #501237

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

jumps

#include "jumps.h"
 
#include <bits/stdc++.h>
using namespace std;
int n;
vector<array<int,20> > pg,ng,hh,mxhh; //prev greater,next greater,highest height,max index reached while taking highest height jumps
//note: mxhh is -1 is jump is invalid, and answer otherwise
vector<int> Hq;
 
int pgq(int st,int x)
{
    while(x>0 && st>-1)
    {
        st=pg[st][__builtin_ctz(x)];
        x^=x&(-x);
    }
    return st;
}
 
int ngq(int st,int x)
{
    while(x>0 && st>-1)
    {
        st=ng[st][__builtin_ctz(x)];
        x^=x&(-x);
    }
    return st;
}
 
int hhq(int st,int x)
{
    while(x>0 && st>-1)
    {
        st=hh[st][__builtin_ctz(x)];
        x^=x&(-x);
    }
    return st;
}
 
int mxhhq(int st,int x)
{
    if(hhq(st,x)==-1)   return -1;
    int res=st;
    while(x>0)
    {
        res=max(res,mxhh[st][__builtin_ctz(x)]);
        st=hh[st][__builtin_ctz(x)];
        x^=x&(-x);
    }
    return res;
}
 
void init(int N, std::vector<int> H) {
    n=N;
    Hq=H;
    pg.resize(N),ng.resize(N),hh.resize(N),mxhh.resize(N);
    stack<int> st;
    pg[0][0]=-1;
    st.push(0);
    for(int i=1;i<N;i++)
    {
        while(!st.empty() && H[st.top()]<H[i])  st.pop();
        if(st.empty())  pg[i][0]=-1;
        else    pg[i][0]=st.top();
        st.push(i);
    }
    while(!st.empty())  st.pop();
    ng[N-1][0]=-1;
    st.push(N-1);
    for(int i=N-2;i>=0;i--)
    {
        while(!st.empty() && H[st.top()]<H[i])  st.pop();
        if(st.empty())  ng[i][0]=-1;
        else    ng[i][0]=st.top();
        st.push(i);
    }
    for(int i=0;i<N;i++)
    {
        int mx=-1,posmx=-1;
        if(pg[i][0]>-1 && H[pg[i][0]]>mx)   mx=H[pg[i][0]],posmx=pg[i][0];
        if(ng[i][0]>-1 && H[ng[i][0]]>mx)   mx=H[ng[i][0]],posmx=ng[i][0];
        hh[i][0]=mxhh[i][0]=posmx;
        if(posmx>-1)    mxhh[i][0]=max(i,posmx);
    }
    for(int j=1;j<20;j++)
    {
        for(int i=0;i<N;i++)
        {
            pg[i][j]=ng[i][j]=hh[i][j]=mxhh[i][j]=-1;
            if(pg[i][j-1]>-1)   pg[i][j]=pg[pg[i][j-1]][j-1];
            if(ng[i][j-1]>-1)   ng[i][j]=ng[ng[i][j-1]][j-1];
            if(hh[i][j-1]>-1)   hh[i][j]=hh[hh[i][j-1]][j-1];
            if(hh[i][j]>-1) mxhh[i][j]=max(mxhh[i][j-1],mxhh[mxhh[i][j-1]][j-1]);
        }
    }
}
 
int minimum_jumps(int A, int B, int C, int D) {
    int l,r,mid,ans; //remember to reset this before each binary search
    int cnt=n;
    //there are two cases
    //Case 1: if i use some go to right only moves, that means i want to reach C
    l=0,r=n-1,ans=-1;
    while(l<=r)
    {
        mid=l+(r-l)/2;
        int pos=pgq(B,mid);
        if(pos==-1 || Hq[pos]>Hq[C])    r=mid-1;
        else
        {
            ans=mid;
            l=mid+1;
        }
    }
    if(ans>-1)
    {
        int posAB=pgq(B,ans);
        int tmp=0;
        l=0,r=n-1,ans=-1;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            int pos=hhq(posAB,mid);
            if(pos==-1 || Hq[pos]>Hq[C])    r=mid-1;
            else
            {
                ans=mid;
                l=mid+1;
            }
        }
        tmp+=ans;
        int cpos=hhq(posAB,ans);
        l=0,r=n-1,ans=-1;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            int pos=ngq(cpos,mid);
            if(pos==-1 || Hq[pos]>Hq[C])    r=mid-1;
            else
            {
                ans=mid;
                l=mid+1;
            }
        }
        tmp+=ans;
        int fpos=ngq(cpos,ans);
        if(fpos==C) cnt=min(cnt,tmp);
    }
    //Case 2: i only take hh jumps until i reach something in [C,D]
    l=0,r=n-1,ans=-1;
    while(l<=r)
    {
        mid=l+(r-l)/2;
        int pos=ngq(C,mid);
        if(pos==-1 || pos>D)    r=mid-1;
        else
        {
            ans=mid;
            l=mid+1;
        }
    }
    int mxCD=Hq[ngq(C,ans)];
    l=0,r=n-1,ans=-1;
    while(l<=r)
    {
        mid=l+(r-l)/2;
        int pos=pgq(B,mid);
        if(pos==-1 || pos<A || Hq[pos]>mxCD)    r=mid-1;
        else
        {
            ans=mid;
            l=mid+1;
        }
    }
    if(ans>-1)
    {
        int tmp=0;
        int posAB=pgq(B,ans);
        l=0,r=n-1,ans=-1;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            int mxpos=mxhhq(posAB,mid),pos=hhq(posAB,mid);
            if(mxpos==-1 || mxpos>D || Hq[pos]>mxCD)    r=mid-1;
            else
            {
                if(mxpos<C) l=mid+1;
                else
                {
                    ans=mid;
                    r=mid-1;
                }
            }
        }
        tmp+=ans;
        int cpos=hhq(posAB,ans);
        l=0,r=n-1,ans=0;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            int pos=ngq(cpos,mid);
            if(pos==-1 || pos>D)    r=mid-1;
            else
            {
                if(pos<C)   l=mid+1;
                else
                {
                    ans=mid;
                    r=mid-1;
                }
            }
        }
        tmp+=ans;
        int fpos=ngq(cpos,ans);
        if(fpos>=C && fpos<=D)    cnt=min(tmp,cnt);
    }
    return ((cnt==n)?-1:cnt);
}

• 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