oj.uz

Submission #501343

# Submission time Handle Problem Language Result Execution time Memory
501343 2022-01-02T20:27:54 Z Newtech66 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 2658 ms 66116 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
            {
                if(mxpos>=C)    ans=mid,r=mid-1;
                else
                {
                    int nxtpos=ng[pos][0];
                    if(nxtpos>=C && nxtpos<=D)  ans=mid,r=mid-1;
                    else
                    {
                        if(nxtpos==-1)  exit(1);
                        else
                        {
                            if(nxtpos<C)    ans=mid,l=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 411 ms 52632 KB Output is correct
4 Correct 2567 ms 66076 KB Output is correct
5 Correct 1650 ms 33428 KB Output is correct
6 Correct 2192 ms 65980 KB Output is correct
7 Correct 1607 ms 45208 KB Output is correct
8 Correct 2658 ms 66116 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 Runtime error 1 ms 328 KB Execution failed because the return code was nonzero
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 Runtime error 1 ms 328 KB Execution failed because the return code was nonzero
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 122 ms 52496 KB Output is correct
6 Correct 144 ms 65328 KB Output is correct
7 Correct 77 ms 33460 KB Output is correct
8 Correct 150 ms 65180 KB Output is correct
9 Correct 18 ms 10084 KB Output is correct
10 Correct 138 ms 65196 KB Output is correct
11 Correct 146 ms 66088 KB Output is correct
12 Correct 128 ms 65884 KB Output is correct
13 Correct 136 ms 65824 KB Output is correct
14 Correct 146 ms 65192 KB Output is correct
15 Correct 189 ms 65644 KB Output is correct
16 Correct 137 ms 65932 KB Output is correct
17 Correct 136 ms 65972 KB Output is correct
18 Correct 0 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 Runtime error 0 ms 328 KB Execution failed because the return code was nonzero
24 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 Runtime error 236 ms 29916 KB Execution failed because the return code was nonzero
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 Runtime error 236 ms 29916 KB Execution failed because the return code was nonzero
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 411 ms 52632 KB Output is correct
4 Correct 2567 ms 66076 KB Output is correct
5 Correct 1650 ms 33428 KB Output is correct
6 Correct 2192 ms 65980 KB Output is correct
7 Correct 1607 ms 45208 KB Output is correct
8 Correct 2658 ms 66116 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 Runtime error 1 ms 328 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -