Submission #1033071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033071		NValchanov	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	868 ms	69332 KiB

jumps

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int MAXLOG = 20;
const int INF = 2e9 + 10;

int n;
int h[MAXN];
int l[MAXN];
int r[MAXN];
int nxt[MAXN];

struct SparseTable
{
    int st[MAXN][MAXLOG];
    int lg[MAXN];

    void build()
    {
        for(int i = 1; i <= n; i++)
        {
            st[i][0] = h[i];
        }
        
        for(int j = 1; (1 << j) <= n; j++)
        {
            for(int i = 1; i + (1 << j) - 1 <= n; i++)
            {
                st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
            }
        }

        for(int i = 2; i <= n; i++)
        {
            lg[i] = lg[i / 2] + 1;
        }
    }

    int query(int left, int right)
    {
        int len = right - left + 1;
        int k = lg[len];

        return max(st[left][k], st[right - (1 << k) + 1][k]);
    }
};

struct BinaryLifting
{
    int lift[MAXN][MAXLOG];

    void build(int par[])
    {
        for(int i = 1; i <= n; i++)
        {
            lift[i][0] = par[i];
        }

        for(int j = 1; (1 << j) <= n; j++)
        {
            for(int i = 1; i <= n; i++)
            {
                lift[i][j] = lift[lift[i][j - 1]][j - 1];
            }
        }
    }

    int anc(int i, int j)
    {
        return lift[i][j];
    }
};

SparseTable sparse;
BinaryLifting goL, goR, goLR;

void fill_l()
{
    stack < int > st;
    st.push(0);

    for(int i = 1; i <= n; i++)
    {
        while(h[st.top()] < h[i])
        {
            st.pop();
        }

        l[i] = st.top();
        st.push(i);
    }

    // cout << endl;
    // cout << "To the left : " << endl;
    // for(int i = 1; i <= n; i++)
    // {
    //     cout << l[i] << " "; 
    // }
    // cout << endl;
}

void fill_r()
{
    stack < int > st;
    st.push(n + 1);

    for(int i = n; i >= 1; i--)
    {
        while(h[st.top()] < h[i])
        {
            st.pop();
        }

        r[i] = st.top();
        st.push(i);
    }

    r[0] = r[n + 1] = n + 1;

    // cout << endl;
    // cout << "To the right : " << endl;
    // for(int i = 1; i <= n; i++)
    // {
    //     cout << r[i] << " "; 
    // }
    // cout << endl;
}

void fill_nxt()
{
    for(int i = 1; i <= n; i++)
    {
        nxt[i] = l[i];
        if(h[r[i]] > h[l[i]])
            nxt[i] = r[i];
    }

    // cout << endl;
    // cout << "To the max : " << endl;
    // for(int i = 1; i <= n; i++)
    // {
    //     cout << nxt[i] << " "; 
    // }
    // cout << endl;
}

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

    h[0] = INF;
    h[n + 1] = INF;

    fill_l();
    fill_r();
    fill_nxt();

    sparse.build();
    goL.build(l);
    goR.build(r);
    goLR.build(nxt);
}

int minimum_jumps(int fromL, int fromR, int toL, int toR)
{
    fromL++;
    fromR++;
    toL++;
    toR++;

    int max_to = sparse.query(toL, toR);
    int max_between = sparse.query(fromR, toL - 1);

    if(max_between > max_to)
        return -1;

    int idx = fromR;

    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        if(goL.anc(idx, j) >= fromL && h[goL.anc(idx, j)] <= max_to)
        {
            idx = goL.anc(idx, j);
        }
    }

    if(goR.anc(idx, 0) >= toL)
        return 1;

    int steps = 0;

    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        if(h[goLR.anc(idx, j)] <= max_to && r[goLR.anc(idx, j)] < toL)
        {
            steps += (1 << j);
            idx = goLR.anc(idx, j);
        }
    }

    if(h[nxt[idx]] <= max_to)
    {
        idx = nxt[idx];
        idx = r[idx];
        steps += 2;

        return steps;
    }

    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        if(r[goR.anc(idx, j)] < toL)
        {
            steps += (1 << j);
            idx = goR.anc(idx, j);
        }
    }

    idx = r[idx];
    idx = r[idx];
    steps += 2;

    return steps;
}

// int main() 
// {
//     int n, q;
//     std::vector <int> h;
//     std::cin >> n >> q;
//     h.resize(n);

//     for (int i = 0 ; i < n ; ++i)
//     {
//         std::cin >> h[i];
//     }

//     std::vector <std::array <int,4>> queries(q);
//     for (int i = 0 ; i < q ; ++i)
//     {
//         std::cin >> queries[i][0] >> queries[i][1] >> queries[i][2] >> queries[i][3];
//     }

//     init(n, h);
//     for (int i = 0 ; i < q ; ++i)
//     {
//         std::cout << minimum_jumps(queries[i][0], queries[i][1], queries[i][2], queries[i][3]) << '\n';
//     }

//     return 0;
// }
/*
7 1
3 2 1 6 4 5 7
4 4 6 6
*/

Compilation message (stderr)

jumps.cpp: In member function 'void SparseTable::build()':
jumps.cpp:35:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |                 st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
      |                                                           ~~^~~

• 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