Submission #645156

#	Time	Username	Problem	Language	Result	Execution time	Memory
645156		Tenis0206	Rainforest Jumps (APIO21_jumps)	C++11	100 / 100	1219 ms	64564 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

int n;
int h[200005];

int l[200005],r[200005];

int Log2[200005];
int rmq[200005][25],u[200005][25],ur[200005][25];

void get_lr()
{
    stack<int> st;
    for(int i=1; i<=n; i++)
    {
        while(!st.empty() && h[i] > h[st.top()])
        {
            st.pop();
        }
        if(st.empty())
        {
            l[i] = 0;
        }
        else
        {
            l[i] = st.top();
        }
        st.push(i);
    }
    while(!st.empty())
    {
        st.pop();
    }
    for(int i=n; i>=1; i--)
    {
        while(!st.empty() && h[i] > h[st.top()])
        {
            st.pop();
        }
        if(st.empty())
        {
            r[i] = 0;
        }
        else
        {
            r[i] = st.top();
        }
        st.push(i);
    }
}

void binary_lifting()
{
    for(int i=2; i<=n; i++)
    {
        Log2[i] = 1 + Log2[i/2];
    }
    for(int i=1; i<=n; i++)
    {
        rmq[i][0] = h[i];
        ur[i][0] = r[i];
        if(!l[i])
        {
            u[i][0] = r[i];
            continue;
        }
        if(!r[i])
        {
            u[i][0] = l[i];
            continue;
        }
        if(h[l[i]] > h[r[i]])
        {
            u[i][0] = l[i];
        }
        else
        {
            u[i][0] = r[i];
        }
    }
    for(int k=1; k<=Log2[n]; k++)
    {
        for(int i=1; i<=n; i++)
        {
            u[i][k] = u[u[i][k-1]][k-1];
            ur[i][k] = ur[ur[i][k-1]][k-1];
            if(i + (1<<k) - 1 <= n)
            {
                rmq[i][k] = max(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);
            }
        }
    }
}

int query_max(int x, int y)
{
    int k = Log2[y - x + 1];
    return max(rmq[x][k],rmq[y-(1<<k)+1][k]);
}

void init(int N, vector<int> H)
{
    n = N;
    for(int i=1; i<=n; i++)
    {
        h[i] = H[i-1];
    }
    get_lr();
    binary_lifting();
}

int get_poz(int a, int b, int c, int d)
{
    int st = a;
    int dr = b;
    int val = 0;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(query_max(mij,b) < query_max(c,d))
        {
            val = query_max(mij,b);
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    st = a;
    dr = b;
    int poz = 0;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(query_max(mij,b)>=val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return poz;
}

int minimum_jumps(int a, int b, int c, int d)
{
    ++a,++b,++c,++d;
    if(query_max(b,c-1) > query_max(c,d))
    {
        return -1;
    }
    int poz = get_poz(a,b,c,d);
    int rez = 0;
    for(int p=Log2[n]; p>=0; p--)
    {
        if(r[u[poz][p]] && r[u[poz][p]]<c)
        {
            rez += (1<<p);
            poz = u[poz][p];
        }
    }
    if(r[poz]>=c)
    {
        ++rez;
        return rez;
    }
    if(r[l[poz]]<=d && r[l[poz]]>=c)
    {
        rez += 2;
        return rez;
    }
    for(int p=Log2[n]; p>=0; p--)
    {
        if(ur[poz][p] && ur[poz][p]<c)
        {
            rez += (1<<p);
            poz = ur[poz][p];
        }
    }
    ++rez;
    poz = r[poz];
    return rez;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19