Submission #567156

#	Time	Username	Problem	Language	Result	Execution time	Memory
567156		Mazaalai	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4059 ms	14712 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair <ll, ll>;
int n;
const int N = 2e5 + 5;
const int INF = 1e6;
int nums[N], L[N], R[N];
vector <int> paths[N];
bool test1;
void init(int _n, vector<int> _nums) {
    test1 = 1;
    n = _n;
    nums[0] = nums[n+1] = INF;
    for (int i = 0; i < n; i++) test1 &= (_nums[i] == i+1);
    for (int i = 1; i <= n; i++) nums[i] = _nums[i-1];
    // for (int i = 1; i <= n; i++) test1 &= (i == nums[i]);
    stack <int> stk;
    stk.push(0);
    for (int i = 1; i <= n; i++) {
        while(nums[stk.top()] < nums[i]) stk.pop();
        L[i] = stk.top();
        stk.push(i);
    }
    while(!stk.empty()) stk.pop();
    stk.push(n+1);
    for (int i = n; i > 0; i--) {
        while(nums[stk.top()] < nums[i]) stk.pop();
        R[i] = stk.top();
        stk.push(i);
    }
    // for (int i = 1; i <= n; i++) {
    //     paths[i].pb(L[i]);
    //     paths[i].pb(R[i]);
        // cout << i << ": " << nums[L[i]] << ' ' << nums[i] << ' ' << nums[R[i]] << '\n';
    // }
}
int C, D;
int dp[N];
int solve(int pos) {
    int& res = dp[pos];
    if (res != -1) return res;
    if (pos == 0 || pos == n+1) return INF;
    if (C <= pos && pos <= D) return 0;
    return res = 1+min(solve(L[pos]), solve(R[pos]));
}
int minimum_jumps(int A, int B, int _C, int _D) {
    C = _C+1;
    D = _D+1;
    if (test1) {
        // cout << "LOL\n";
        return _C - B;
    }
    int ans = INF;
    for (int i = 0; i <= n+1; i++) dp[i] = -1;
    for (int i = A+1; i <= B+1; i++) {
        ans = min(ans, solve(i));
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << solve(i) << " \n"[i==n];
    // }
    return ans == INF ? -1 : ans;
}

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