제출 #794036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794036		RecursiveCo	밀림 점프 (APIO21_jumps)	C++14	44 / 100	1349 ms	115368 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;
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 minimum_jumps(int a, int b, int c, int d) {
    if (c != d) return -1; // this is a temporary thing since I'm only implementing C=D.
    if (lpts[c].second >= b) return -1;
    int l = max(lpts[c].second + 1, a);
    int r = b;
    int sz = r - l + 1;
    int j = 0;
    int thepower = 1;
    while (thepower <= sz) thepower *= 2, j++;
    thepower /= 2;
    j--;
    int leftmax = sparse[l][j];
    int rightmax = sparse[r - thepower + 1][j];
    int maximum = max(leftmax, rightmax);

    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;
}

컴파일 시 표준 에러 (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:34:5: note: in expansion of macro 'forto'
   34 |     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:47:5: note: in expansion of macro 'forto'
   47 |     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:59:5: note: in expansion of macro 'forto'
   59 |     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:70:5: note: in expansion of macro 'forto'
   70 |     forto(n, i) arr.push_back(nums[i]), ind[nums[i]] = i;
      |     ^~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:101:9: warning: unused variable 'sheight' [-Wunused-variable]
  101 |     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: 21 / 21
• Subtask 7: 0 / 19