Submission #569197

#	Time	Username	Problem	Language	Result	Execution time	Memory
569197		hibiki	Rainforest Jumps (APIO21_jumps)	C++11	100 / 100	1214 ms	77952 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define f first
#define s second

int n,h[200005];

int bk[200005][20];
vector<int> jp[200005];
void monotone_q_and_lds()
{
    for(int i = 0; i < n; i++)
        bk[i][0] = i;
    stack<int> s;
    for(int i = 0; i < n; i++)
    {
        if(s.size())
        while(!s.empty() && h[s.top()] < h[i])
        {
            // s top go right that is i
            jp[s.top()].pb(i);
            s.pop();
        }
        if(!s.empty())
        {
            // i go left that is s top
            jp[i].pb(s.top());
            bk[i][0] = s.top();
        }
        s.push(i);
    }
}

int spa[2][200005][20];
void gen_spa()
{
    memset(spa,-1,sizeof(spa));
    for(int i = 0; i < n; i++)
    {
        if(sz(jp[i]) > 0)
            spa[0][i][0] = jp[i][0];
        if(sz(jp[i]) > 1)
            spa[1][i][0] = jp[i][1];
    }
    for(int j = 1; j < 20; j++)
    {
        for(int i = 0; i < n; i++)
        {
            if(spa[0][i][j - 1] != -1)
                spa[0][i][j] = spa[0][spa[0][i][j - 1]][j - 1];
            if(spa[1][i][j - 1] != -1)
                spa[1][i][j] = spa[1][spa[1][i][j - 1]][j - 1];
            bk[i][j] = bk[bk[i][j - 1]][j - 1];
        }
    }
}

int rmq[200005][20];
int pre_len[200005];
void gen_rmq()
{
    memset(rmq,0,sizeof(rmq));
    for(int i = 0; i < n; i++)
        rmq[i][0] = h[i];
    for(int j = 1; j < 20; j++)
    {
        for(int i = 0; i < n; i++)
        {
            if(i + (1 << j) - 1 >= n) continue;
            int mid = i + (1 << (j - 1));
            rmq[i][j] = max(rmq[i][j - 1], rmq[mid][j - 1]);
        }
    }
    pre_len[1] = 0;
    for(int i = 2; i < 200005; i++)
    {
        pre_len[i] = pre_len[i - 1];
        if(i == (1 << (pre_len[i] + 1))) pre_len[i]++;
    }
}

void init(int N, vector<int> H)
{
    // input
    n = N;
    for(int i = 0; i < n; i++)
        h[i] = H[i];
    // jump
    monotone_q_and_lds();
    for(int i = 0; i < n; i++)
        sort(all(jp[i]), [&](const int &x, const int &y) {
            return h[x] < h[y];
        });
    // jump sparse table
    gen_spa();
    // rmq
    gen_rmq();
}

int qu_rmq(int l,int r)
{
    int qu_sz = pre_len[r - l + 1];
    int mid = r - (1 << qu_sz) + 1;
    return max(rmq[l][qu_sz], rmq[mid][qu_sz]);
}

int qu_mx_s(int l,int r,int mx)
{
    int ret = r;
    for(int j = 19; j >=0; j--)
    {
        if(l <= bk[ret][j] && h[bk[ret][j]] < mx)
            ret = bk[ret][j];
    }
    return ret;
}

int qu_mn_step(int s,int mx,int mxmost)
{
    int nw = s;
    int ret = 0;
    for(int j = 19; j >= 0; j--)
    {
        if(spa[1][nw][j] == -1) continue;
        if(h[spa[1][nw][j]] < mx)
            nw = spa[1][nw][j], ret += (1 << j);
    }
    if(spa[1][nw][0] != -1 && h[spa[1][nw][0]] < mxmost) return ret + 2;
    for(int j = 19; j >= 0; j--)
    {
        if(spa[0][nw][j] == -1) continue;
        if(h[spa[0][nw][j]] < mx)
            nw = spa[0][nw][j], ret += (1 << j);
    }
    return ret + 2;
}

int minimum_jumps(int A, int B, int C, int D)
{
    int mxe = qu_rmq(C, D);
    int s = qu_mx_s(A, B, mxe);
    if(h[s] > mxe) return -1; // 3 a b
    if(B + 1 == C) return 1;
    int mxmid = qu_rmq(B + 1, C - 1);
    if(mxmid > mxe) return -1; // a 3 b
    if(h[s] > mxmid) return 1; // 2 1 3
    return qu_mn_step(s, mxmid, mxe); // 1 2 3
}

• 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