Submission #672109

#	Time	Username	Problem	Language	Result	Execution time	Memory
672109		c2zi6	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	1 ms	336 KiB

jumps

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

int n;
vector<int> h;
vector<int> minV;
vector<int> maxV;
vector<vector<int>> liftingMin;
vector<vector<int>> liftingMax;

void init(int N, std::vector<int> H) {
    n = N, h = H;
    minV = maxV = vector<int>(n);
    liftingMin = liftingMax = vector<vector<int>>(n, vector<int>(30, -1));

    {
        stack<pair<int, int>> st;
        st.push({1e9, -1});
        for (int i = 0; i < n; i++) {
            while (st.top().first < h[i]) st.pop();
            minV[i] = st.top().second;
            st.push({h[i], i});
        }
    }
    {
        stack<pair<int, int>> st;
        st.push({1e9, -1});
        for (int i = n-1; i >= 0; i--) {
            while (st.top().first < h[i]) st.pop();
            maxV[i] = st.top().second;
            st.push({h[i], i});
        }
    }

    //for (int x : minV) cout << x << " "; cout << endl;
    //for (int x : maxV) cout << x << " "; cout << endl;
    //return;
    for (int i = 0; i < n; i++) {
        if (minV[i] == -1 && maxV[i] == -1) continue;
        if (minV[i] == -1) {
            minV[i] = maxV[i];
        } else if (maxV[i] == -1) {
            maxV[i] = minV[i];
        } else if (h[minV[i]] > h[maxV[i]]) swap(minV[i], maxV[i]);
    }

    //for (int x : minV) cout << x << " "; cout << endl;
    //for (int x : maxV) cout << x << " "; cout << endl;

    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++) v.push_back({h[i], i});
    sort(v.rbegin(), v.rend());

    for (int j = 1; j < n; j++) {
        int i = v[j].second;
        liftingMin[i][0] = minV[i];
        liftingMax[i][0] = maxV[i];
        for (int j = 1; j < 30; j++) {
            if (liftingMin[i][j-1] != -1) liftingMin[i][j] = liftingMin[liftingMin[i][j-1]][j-1];
            if (liftingMax[i][j-1] != -1) liftingMax[i][j] = liftingMax[liftingMax[i][j-1]][j-1];
        }
    }
    //for (int i = 0; i < n; i++) {
    //    for (int j = 0; j < 5; j++) cout << liftingMax[i][j] << " ";
    //    cout << endl;
    //}
}

pair<int, int> blift(vector<vector<int>>& g, int u, int v) {
    for (int i = -1; i < 30; i++) {
        if (g[u][i + 1] == -1 || h[g[u][i + 1]] > h[v]) {
            if (i == -1) return {0, u};
            else return {(1<<i) + blift(g, g[u][i], v).first, g[u][i]};
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (A == B && C == D) {
        A--, B--, C--, D--;
        pair<int, int> p = blift(liftingMax, A, D);
        pair<int, int> q = blift(liftingMin, p.second, D);
        if (h[q.second] != h[D]) return -1;
        else return p.first + q.first;
    }
    return 0;
}

//7 0
//3 2 1 6 4 5 7

int main2() {
  int N, Q;
  //assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  N = 7;
  Q = 10000;
  H = vector<int>{3, 2, 1, 6, 4, 5, 7};
  for (int i = 0; i < N; ++i) {
    //assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'std::pair<int, int> blift(std::vector<std::vector<int> >&, int, int)':
jumps.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
   76 | }
      | ^
jumps.cpp: In function 'int main2()':
jumps.cpp:95:23: warning: 'N' is used uninitialized in this function [-Wuninitialized]
   95 |   std::vector<int> H(N);
      |                       ^

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