oj.uz

Submission #501106

# Submission time Handle Problem Language Result Execution time Memory
501106 2022-01-02T11:17:13 Z Newtech66 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 3025 ms 81836 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);
    }
    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<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-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.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 406 ms 65172 KB Output is correct
4 Correct 2742 ms 81704 KB Output is correct
5 Correct 2335 ms 41252 KB Output is correct
6 Correct 3025 ms 81628 KB Output is correct
7 Correct 1944 ms 55928 KB Output is correct
8 Correct 2632 ms 81740 KB Output is correct

Subtask #2
0 / 8.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 2 ms 200 KB Output is correct
6 Incorrect 3 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 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 2 ms 200 KB Output is correct
6 Incorrect 3 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 1 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 178 ms 65152 KB Output is correct
6 Correct 195 ms 80788 KB Output is correct
7 Correct 99 ms 41536 KB Output is correct
8 Correct 201 ms 80788 KB Output is correct
9 Correct 28 ms 12360 KB Output is correct
10 Correct 203 ms 80928 KB Output is correct
11 Correct 225 ms 81836 KB Output is correct
12 Correct 183 ms 81472 KB Output is correct
13 Incorrect 184 ms 81524 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 362 ms 37056 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 362 ms 37056 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 406 ms 65172 KB Output is correct
4 Correct 2742 ms 81704 KB Output is correct
5 Correct 2335 ms 41252 KB Output is correct
6 Correct 3025 ms 81628 KB Output is correct
7 Correct 1944 ms 55928 KB Output is correct
8 Correct 2632 ms 81740 KB Output is correct
9 Correct 0 ms 200 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 3 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -