Submission #793150

#	Time	Username	Problem	Language	Result	Execution time	Memory
793150		RecursiveCo	Rainforest Jumps (APIO21_jumps)	C++14	23 / 100	1161 ms	83520 KiB

jumps

// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

//#define int long long

vector<pair<int, int>> lpts;
vector<pair<int, int>> rpts;
vector<pair<int, int>> maxima;
vector<vector<pair<int, int>>> greedylift;
vector<vector<pair<int, int>>> rightlift;
vector<int> arr;

void init(int n, vector<int> nums) {
    lpts.resize(n);
    rpts.resize(n);
    maxima.resize(n);
    stack<pair<int, int>> st;
    forto(n, i) {
        while (!st.empty() && st.top().first < nums[i]) st.pop();
        if (st.empty()) lpts[i] = {1e18, -1};
        else lpts[i] = {st.top().first, st.top().second};
        st.push({nums[i], i});
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && st.top().first < nums[i]) st.pop();
        if (st.empty()) rpts[i] = {1e18, -1};
        else rpts[i] = {st.top().first, st.top().second};
        st.push({nums[i], i});
    }
    forto(n, i) maxima[i] = max(lpts[i], rpts[i]);
    // Binary lifting.
    greedylift.resize(n, vector<pair<int, int>>(19, {1e18, -1}));
    rightlift.resize(n, vector<pair<int, int>>(19, {1e18, -1}));
    for (int i = n - 1; i >= 0; i--) {
        rightlift[i][0] = rpts[i];
        for (int j = 1; j < 19; j++) {
            if (rightlift[i][j - 1].second == -1) break;
            rightlift[i][j] = rightlift[rightlift[i][j - 1].second][j - 1];
        }
    }
    vector<pair<int, int>> sorted;
    forto(n, i) sorted.push_back({nums[i], i});
    sortl(sorted);
    for (int ip = n - 1; ip >= 0; ip--) {
        int i = sorted[ip].second;
        greedylift[i][0] = maxima[i];
        for (int j = 1; j < 19; j++) {
            if (greedylift[i][j - 1].second == -1) break;
            greedylift[i][j] = greedylift[greedylift[i][j - 1].second][j - 1];
        }
    }

    forto(n, i) arr.push_back(nums[i]);
}

int minimum_jumps(int a, int b, int c, int d) {
    if (a != b || c != d) return -1; // this is a temporary thing since I'm only implementing A=B; C=D.
    int S = a;
    int T = c;
    int sheight = arr[S];
    int theight = arr[T];
    int steps = 0;
    int power = 1 << 18;
    int blift = 18;
    int index = S;
    while (blift >= 0) {
        auto dest = greedylift[index][blift];
        if (dest.first <= theight && dest.second != -1) {
            steps += power;
            index = dest.second;
        }
        blift--;
        power /= 2;
    }
    power = 1 << 18;
    blift = 18;
    while (blift >= 0) {
        auto dest = rightlift[index][blift];
        if (dest.first <= theight && dest.second != -1) {
            steps += power;
            index = dest.second;
        }
        blift--;
        power /= 2;
    }
    if (arr[index] == theight) return steps;
    else return -1;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:32:5: note: in expansion of macro 'forto'
   32 |     forto(n, i) {
      |     ^~~~~
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:45:5: note: in expansion of macro 'forto'
   45 |     forto(n, i) maxima[i] = max(lpts[i], rpts[i]);
      |     ^~~~~
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:57:5: note: in expansion of macro 'forto'
   57 |     forto(n, i) sorted.push_back({nums[i], i});
      |     ^~~~~
jumps.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
jumps.cpp:68:5: note: in expansion of macro 'forto'
   68 |     forto(n, i) arr.push_back(nums[i]);
      |     ^~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:75:9: warning: unused variable 'sheight' [-Wunused-variable]
   75 |     int sheight = arr[S];
      |         ^~~~~~~

• 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