Submission #471902

#	Time	Username	Problem	Language	Result	Execution time	Memory
471902		qwerasdfzxcl	Rainforest Jumps (APIO21_jumps)	C++14	23 / 100	1912 ms	135856 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> sp1[200200], sp2[200200], sp3[200200], sp4[200200], a;
int n, l[200200], r[200200];

int geth(int x){
    if (x<0) return -1e9;
    if (x>=n) return -1e9;
    return a[x];
}

void init(int N, std::vector<int> H) {
    n = N, a = H;
    for (int i=0;i<n;i++){
        sp1[i].push_back(H[i]);
        sp2[i].push_back(H[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (i-(1<<j)+1<0) sp1[i].push_back(-1);
            else sp1[i].push_back(max(sp1[i][j-1], sp1[i-(1<<(j-1))][j-1]));
            if (i+(1<<j)-1>=n) sp2[i].push_back(-1);
            else sp2[i].push_back(max(sp2[i][j-1], sp2[i+(1<<(j-1))][j-1]));
        }
    }
    for (int i=0;i<n;i++){
        int cur = i-1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=-1 && sp1[cur][j]!=-1 && max(cur2, sp1[cur][j])<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur -= (1<<j);
        }
        l[i] = cur; cur = i+1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=n && sp2[cur][j]!=-1 && sp2[cur][j]<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur += (1<<j);
        }
        r[i] = cur;
        if (geth(l[i])>=geth(r[i])) sp3[i].push_back(l[i]);
        else sp3[i].push_back(r[i]);
        sp4[i].push_back(r[i]);
        //printf("%d %d\n", l[i], r[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (sp3[i][j-1]==-1) sp3[i].push_back(-1);
            else sp3[i].push_back(sp3[sp3[i][j-1]][j-1]);
            if (sp4[i][j-1]==n) sp4[i].push_back(n);
            else sp4[i].push_back(sp4[sp4[i][j-1]][j-1]);
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int cur = A, ans = 0;
    for (int j=19;j>=0;j--) if (sp3[cur][j]!=-1 && a[sp3[cur][j]]<a[C]) cur = sp3[cur][j], ans += (1<<j);
    for (int j=19;j>=0;j--) if (sp4[cur][j]!=n && a[sp4[cur][j]]<=a[C]) cur = sp4[cur][j], ans += (1<<j);
    if (cur!=C) return -1;
    return ans;
}

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