Submission #794252

#	Time	Username	Problem	Language	Result	Execution time	Memory
794252		RecursiveCo	Rainforest Jumps (APIO21_jumps)	C++14	81 / 100	4097 ms	116332 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<vector<int>> sparse;
vector<int> arr;
vector<int> lg;
vector<int> pow2;
map<int, int> ind;
bool ez = true;

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] = {2e9, -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] = {2e9, -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, {2e9, -1}));
    rightlift.resize(n, vector<pair<int, int>>(19, {2e9, -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]), ind[nums[i]] = i;
        if (nums[i] != i + 1) ez = false;
    }

    sparse.resize(n, vector<int>(19, 0));
    for (int i = n - 1; i >= 0; i--) {
        sparse[i][0] = arr[i];
        int power = 1;
        for (int j = 1; j < 19; j++) {
            power *= 2;
            if (i + power > n) break;
            sparse[i][j] = max(sparse[i][j - 1], sparse[i + power / 2][j - 1]);
        }
    }

    int logval = -1;
    int logpow = 1;
    lg.resize(n + 1, -1);
    forto(n + 1, i) {
        if (i == 0) continue;
        if (i == logpow) {
            logpow *= 2;
            logval++;
        }
        lg[i] = logval;
    }

    forto(19, i) {
        if (i == 0) pow2.push_back(1);
        else pow2.push_back(pow2.back() * 2);
    }
}

int query(int l, int r) {
    int sz = r - l + 1;
    int j = lg[sz];
    int thepower = pow2[j];
    int leftmax = sparse[l][j];
    int rightmax = sparse[r - thepower + 1][j];
    return max(leftmax, rightmax);
}

int minimum_jumps(int a, int b, int c, int d) {
    if (ez) return c - b;
    int answer = 2e9;
    for (int C = c; C <= d; C++) {
        if (lpts[C].second >= b) continue;
        int l = max(lpts[C].second + 1, a);
        int r = b;
        int maximum = query(l, r);

        int S = ind[maximum];
        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) answer = min(answer, steps);
    }
    if (answer != 2e9) return answer;
    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:37:5: note: in expansion of macro 'forto'
   37 |     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:50:5: note: in expansion of macro 'forto'
   50 |     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:62:5: note: in expansion of macro 'forto'
   62 |     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:73:5: note: in expansion of macro 'forto'
   73 |     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:92:5: note: in expansion of macro 'forto'
   92 |     forto(n + 1, 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:101:5: note: in expansion of macro 'forto'
  101 |     forto(19, i) {
      |     ^~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:127:13: warning: unused variable 'sheight' [-Wunused-variable]
  127 |         int sheight = arr[S];
      |             ^~~~~~~

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