oj.uz

Submission #501099

# Submission time Handle Problem Language Result Execution time Memory
501099 2022-01-02T11:12:18 Z Newtech66 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 2764 ms 81800 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
int n;
vector<array<int,25> > 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&(-x);
    }
    return st;
}

int ngq(int st,int x)
{
    while(x>0 && st>-1)
    {
        st=ng[st][__builtin_ctz(x&(-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&(-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&(-x))]);
        st=hh[st][__builtin_ctz(x&(-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<25;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],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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 417 ms 65112 KB Output is correct
4 Correct 2646 ms 81744 KB Output is correct
5 Correct 1746 ms 41236 KB Output is correct
6 Correct 2764 ms 81800 KB Output is correct
7 Correct 1863 ms 55828 KB Output is correct
8 Correct 2667 ms 81676 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 2 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 2 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

# Verdict Execution time Memory 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 150 ms 65032 KB Output is correct
6 Correct 187 ms 80924 KB Output is correct
7 Correct 100 ms 41536 KB Output is correct
8 Correct 181 ms 80900 KB Output is correct
9 Correct 26 ms 12480 KB Output is correct
10 Correct 183 ms 80788 KB Output is correct
11 Correct 183 ms 81668 KB Output is correct
12 Correct 181 ms 81412 KB Output is correct
13 Incorrect 181 ms 81392 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory 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 Incorrect 301 ms 37140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory 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 Incorrect 301 ms 37140 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 417 ms 65112 KB Output is correct
4 Correct 2646 ms 81744 KB Output is correct
5 Correct 1746 ms 41236 KB Output is correct
6 Correct 2764 ms 81800 KB Output is correct
7 Correct 1863 ms 55828 KB Output is correct
8 Correct 2667 ms 81676 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 0 ms 200 KB Output is correct
13 Correct 2 ms 200 KB Output is correct
14 Incorrect 2 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -