Submission #672141

#	Time	Username	Problem	Language	Result	Execution time	Memory
672141		c2zi6	Rainforest Jumps (APIO21_jumps)	C++14	60 / 100	4089 ms	67656 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;
bool subtask1 = true;

void init(int N, std::vector<int> H) {
    n = N, h = H;
    for (int i = 0; i < n; i++) {
        if (h[i] != i + 1) {
            subtask1 = false;
            break;
        }
    }
    if (subtask1) return;

    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 {
                //cout << "END AT " << g[u][i] << endl;
                pair<int, int> p = blift(g, g[u][i], v);
                return {(1<<i) + p.first, p.second};
            }
        }
    }
}

vector<int> dp;
int dpf(int i) {
    if (dp[i] != -1) return dp[i];
    if (minV[i] == -1) return dp[i] = 2e9;
    return dp[i] = min(dpf(minV[i]), dpf(maxV[i])) + 1;
}

int minimum_jumps(int A, int B, int C, int D) {
    if (subtask1) {
        //cout << "SIK ASHXATAV" << endl;
        return C - B;
    } else if (A == B && C == D) {
        pair<int, int> p = blift(liftingMax, A, D);
        //cout << p.first << " " << p.second << endl;
        pair<int, int> q = blift(liftingMin, p.second, D);
        if (h[q.second] != h[D]) return -1;
        else return p.first + q.first;
    } else {
        dp = vector<int>(n, -1);
        for (int i = C; i <= D; i++) dp[i] = 0;

        int mn = 2e9;
        for (int i = A; i <= B; i++) {
            //cout << dpf(i) << endl;
            mn = min(mn, dpf(i));
        }
        if (mn == 2e9) return -1;
        return mn;
    }
}

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

int mainq() {
  int N, Q;
  //assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  N = 7;
  Q = 10000;
  H = vector<int>{1, 2, 3, 4, 5, 6, 7};
  //H = vector<int>{3, 2, 1, 6, 4, 5, 7, 8, 10, 12, 11, 9};
  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:89:1: warning: control reaches end of non-void function [-Wreturn-type]
   89 | }
      | ^
jumps.cpp: In function 'int mainq()':
jumps.cpp:128:23: warning: 'N' is used uninitialized in this function [-Wuninitialized]
  128 |   std::vector<int> H(N);
      |                       ^

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