Submission #794120

#	Time	Username	Problem	Language	Result	Execution time	Memory
794120		RecursiveCo	Rainforest Jumps (APIO21_jumps)	C++14	48 / 100	1289 ms	116264 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;

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;

    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 (query(c, d) < arr[b]) return -1;
    int ll = c;
    int rr = d;
    while (rr - ll >= 1) {
        int middle = (ll + rr) / 2;
        if (query(c, middle) < arr[b]) ll = middle + 1;
        else rr = middle;
    }
    c = ll;
    if (lpts[c].second >= b) return -1;
    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) 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:36:5: note: in expansion of macro 'forto'
   36 |     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:49:5: note: in expansion of macro 'forto'
   49 |     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:61:5: note: in expansion of macro 'forto'
   61 |     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:72:5: note: in expansion of macro 'forto'
   72 |     forto(n, i) arr.push_back(nums[i]), ind[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:88:5: note: in expansion of macro 'forto'
   88 |     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:97:5: note: in expansion of macro 'forto'
   97 |     forto(19, i) {
      |     ^~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:129:9: warning: unused variable 'sheight' [-Wunused-variable]
  129 |     int sheight = arr[S];
      |         ^~~~~~~

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