oj.uz

Submission #501109

# Submission time Handle Problem Language Result Execution time Memory
501109 2022-01-02T11:22:11 Z Newtech66 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 2400 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]
    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 336 ms 52616 KB Output is correct
4 Correct 2356 ms 66092 KB Output is correct
5 Correct 1524 ms 33420 KB Output is correct
6 Correct 2400 ms 66092 KB Output is correct
7 Correct 1720 ms 45200 KB Output is correct
8 Correct 2291 ms 66092 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 216 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 216 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 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 112 ms 52528 KB Output is correct
6 Correct 138 ms 65296 KB Output is correct
7 Correct 81 ms 33548 KB Output is correct
8 Correct 142 ms 65216 KB Output is correct
9 Correct 18 ms 10096 KB Output is correct
10 Correct 137 ms 65192 KB Output is correct
11 Correct 138 ms 65972 KB Output is correct
12 Correct 141 ms 65940 KB Output is correct
13 Incorrect 132 ms 65824 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 1 ms 200 KB Output is correct
4 Incorrect 299 ms 29920 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 1 ms 200 KB Output is correct
4 Incorrect 299 ms 29920 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 336 ms 52616 KB Output is correct
4 Correct 2356 ms 66092 KB Output is correct
5 Correct 1524 ms 33420 KB Output is correct
6 Correct 2400 ms 66092 KB Output is correct
7 Correct 1720 ms 45200 KB Output is correct
8 Correct 2291 ms 66092 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 216 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 -