Submission #939966

#	Time	Username	Problem	Language	Result	Execution time	Memory
939966		bobbilyking	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4038 ms	17656 KiB

jumps

#include "jumps.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }

template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }

const ll NN = 2e5 + 10;
const ll INF = 1e9 + 1;
ll n;

vl graph[NN];


void init(int _N, std::vector<int> H) {
    n = _N;
    vl lst(n);
    F(i, 0, n) {
        lst[i] = i - 1;
        while (lst[i] != -1 and H[lst[i]] < H[i]) lst[i] = lst[lst[i]];
        if (lst[i] != -1) graph[i].push_back(lst[i]);
    }
    FD(i, n-1, -1) {
        lst[i] = i + 1;
        while (lst[i] != n and H[lst[i]] < H[i]) lst[i] = lst[lst[i]];
        if (lst[i] != n) graph[i].push_back(lst[i]);
    }
    


}

int minimum_jumps(int A, int B, int C, int D) {
   vl dist(n, INF);

    vl q;
    F(i, A, B+1) q.push_back(i), dist[i] = 0;

    while (q.size()) for (auto i: exchange(q, {})) {
        for (auto x: graph[i]) if (dist[i] + 1 < dist[x]) {
            dist[x] = dist[i] + 1; q.push_back(x);
        }
    }

    ll res = *min_element(dist.begin() + C, dist.begin() +D + 1);

    return res == INF ? -1: res;
}

• Subtask 1: 0 / 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