제출 #501109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501109		Newtech66	밀림 점프 (APIO21_jumps)	C++17	4 / 100	2400 ms	66092 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]);
        }
    }
    //for(int i=0;i<N;i++)    cout<<pg[i][0]<<" ";
    //cout<<endl;
    //for(int i=0;i<N;i++)    cout<<ng[i][0]<<" ";
    //cout<<endl;
}

int minimum_jumps(int A, int B, int C, int D) {
    int l,r,mid,ans; //remember to reset this before each binary search
    //find max 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)];
    //cout<<mxCD<<" ";
    //find max in [A,B]<=max in [C,D] and not shadowed
    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) return ans;
    int posAB=pgq(B,ans);
    //cout<<posAB<<" ";
    //^from here, first keep taking highest height jumps until you can't anymore, then keep jumping right until you reach something in [C,D]
    l=0,r=n-1,ans=0;
    int cnt=0;
    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;
            }
        }
    }
    cnt+=ans;
    int cpos=hhq(posAB,ans);
    //cout<<cpos<<" ";
    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;
            }
        }
    }
    cnt+=ans;
    int fpos=ngq(cpos,ans);
    //cout<<fpos<<" ";
    if(fpos<C || fpos>D)    return -1;
    return 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