oj.uz

Submission #501328

# Submission time Handle Problem Language Result Execution time Memory
501328 2022-01-02T19:45:38 Z Newtech66 Rainforest Jumps (APIO21_jumps) C++17
16 / 100
 2796 ms 66108 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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]);
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int l,r,mid,ans; //remember to reset this before each binary search
    int cnt=n;
    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<<endl;
    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)
    {
        //cout<<"Case 2: ";
        int tmp=0;
        int posAB=pgq(B,ans);
        l=0,r=n-1,ans=-1;
        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
            {
                int nxtpos=ng[pos][0];
                if(nxtpos==-1)
                {
                    if(mxpos>D) r=mid-1;
                    else if(mxpos>=C && mxpos<=D)   ans=mid,r=mid-1;
                    else    r=mid-1;
                }else
                {
                    if(nxtpos<C)    ans=mid,l=mid+1;
                    else if(nxtpos<=D)  ans=mid,r=mid-1;
                    else
                    {
                        if(mxpos>D) r=mid-1;
                        else if(mxpos>=C && mxpos<=D)   ans=mid,r=mid-1;
                        else    r=mid-1;
                    }
                }
            }
        }
        tmp+=ans;
        //cout<<tmp<<endl;
        int cpos=hhq(posAB,ans);
        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;
                }
            }
        }
        tmp+=ans;
        int fpos=ngq(cpos,ans);
        //cout<<posAB<<" "<<cpos<<" "<<fpos<<" "<<tmp<<endl;
        if(fpos>=C && fpos<=D)    cnt=min(tmp,cnt);
    }
    return ((cnt==n)?-1: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 362 ms 52624 KB Output is correct
4 Correct 2423 ms 66088 KB Output is correct
5 Correct 1805 ms 33364 KB Output is correct
6 Correct 2721 ms 66036 KB Output is correct
7 Correct 1832 ms 45236 KB Output is correct
8 Correct 2796 ms 66096 KB Output is correct

Subtask #2
0 / 8.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 1 ms 200 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 3 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 2 ms 328 KB Output is correct
12 Correct 3 ms 328 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 3 ms 328 KB Output is correct
15 Incorrect 2 ms 328 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 1 ms 200 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 3 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 3 ms 328 KB Output is correct
11 Correct 2 ms 328 KB Output is correct
12 Correct 3 ms 328 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 3 ms 328 KB Output is correct
15 Incorrect 2 ms 328 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
12.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 126 ms 52504 KB Output is correct
6 Correct 153 ms 65200 KB Output is correct
7 Correct 78 ms 33464 KB Output is correct
8 Correct 163 ms 65188 KB Output is correct
9 Correct 21 ms 10028 KB Output is correct
10 Correct 137 ms 65196 KB Output is correct
11 Correct 140 ms 66108 KB Output is correct
12 Correct 158 ms 65876 KB Output is correct
13 Correct 137 ms 65860 KB Output is correct
14 Correct 140 ms 65268 KB Output is correct
15 Correct 196 ms 65680 KB Output is correct
16 Correct 153 ms 65940 KB Output is correct
17 Correct 176 ms 65924 KB Output is correct
18 Correct 1 ms 200 KB Output is correct
19 Correct 0 ms 328 KB Output is correct
20 Correct 0 ms 328 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 0 ms 328 KB Output is correct
23 Correct 0 ms 328 KB Output is correct
24 Correct 1 ms 328 KB Output is correct
25 Correct 0 ms 328 KB Output is correct
26 Correct 1 ms 584 KB Output is correct
27 Correct 1 ms 968 KB Output is correct
28 Correct 1 ms 968 KB Output is correct
29 Correct 1 ms 968 KB Output is correct
30 Correct 1 ms 968 KB Output is correct
31 Correct 2 ms 968 KB Output is correct
32 Correct 0 ms 200 KB Output is correct
33 Correct 144 ms 65140 KB Output is correct
34 Correct 143 ms 65232 KB Output is correct
35 Correct 139 ms 65972 KB Output is correct
36 Correct 158 ms 65160 KB Output is correct
37 Correct 168 ms 65636 KB Output is correct
38 Correct 142 ms 65984 KB Output is correct
39 Correct 0 ms 200 KB Output is correct
40 Correct 89 ms 37952 KB Output is correct
41 Correct 140 ms 65200 KB Output is correct
42 Correct 169 ms 65948 KB Output is correct
43 Correct 146 ms 65172 KB Output is correct
44 Correct 171 ms 65792 KB Output is correct
45 Correct 141 ms 66092 KB Output is correct

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 332 ms 29992 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 332 ms 29992 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 362 ms 52624 KB Output is correct
4 Correct 2423 ms 66088 KB Output is correct
5 Correct 1805 ms 33364 KB Output is correct
6 Correct 2721 ms 66036 KB Output is correct
7 Correct 1832 ms 45236 KB Output is correct
8 Correct 2796 ms 66096 KB Output is correct
9 Correct 1 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 1 ms 200 KB Output is correct
14 Correct 3 ms 328 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 3 ms 328 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 3 ms 328 KB Output is correct
19 Correct 2 ms 328 KB Output is correct
20 Correct 3 ms 328 KB Output is correct
21 Correct 2 ms 328 KB Output is correct
22 Correct 3 ms 328 KB Output is correct
23 Incorrect 2 ms 328 KB Output isn't correct
24 Halted 0 ms 0 KB -