oj.uz

답안 #501118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501118 2022-01-02T11:38:22 Z Newtech66 밀림 점프 (APIO21_jumps) C++17
0 / 100
 4000 ms 66092 KB 
#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]
    int cnt=0,curpos=posAB;
    while(curpos<C)
    {
        int nxtpos=hh[curpos][0];
        if(nxtpos==-1)  return -1;
        if(Hq[nxtpos]>mxCD) nxtpos=ng[curpos][0];
        if(nxtpos==-1)  return -1;
        if(nxtpos>D)    return -1;
        curpos=nxtpos;
        cnt++;
    }
    return cnt;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 2781 ms 52652 KB Output is correct
4 Execution timed out 4038 ms 66092 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Incorrect 2 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Incorrect 2 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 110 ms 52500 KB Output is correct
6 Correct 136 ms 65196 KB Output is correct
7 Correct 70 ms 33436 KB Output is correct
8 Correct 146 ms 65320 KB Output is correct
9 Correct 17 ms 10100 KB Output is correct
10 Correct 135 ms 65172 KB Output is correct
11 Correct 153 ms 66056 KB Output is correct
12 Correct 163 ms 65936 KB Output is correct
13 Correct 153 ms 65824 KB Output is correct
14 Correct 138 ms 65164 KB Output is correct
15 Incorrect 191 ms 65552 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 303 ms 29972 KB Output is correct
5 Correct 1145 ms 65168 KB Output is correct
6 Correct 688 ms 10900 KB Output is correct
7 Correct 954 ms 65160 KB Output is correct
8 Correct 489 ms 22592 KB Output is correct
9 Correct 1156 ms 65160 KB Output is correct
10 Execution timed out 4067 ms 66088 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 303 ms 29972 KB Output is correct
5 Correct 1145 ms 65168 KB Output is correct
6 Correct 688 ms 10900 KB Output is correct
7 Correct 954 ms 65160 KB Output is correct
8 Correct 489 ms 22592 KB Output is correct
9 Correct 1156 ms 65160 KB Output is correct
10 Execution timed out 4067 ms 66088 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 2781 ms 52652 KB Output is correct
4 Execution timed out 4038 ms 66092 KB Time limit exceeded
5 Halted 0 ms 0 KB -