Submission #805066

#	Time	Username	Problem	Language	Result	Execution time	Memory
805066		radaiosm7	Rainforest Jumps (APIO21_jumps)	C++11	4 / 100	844 ms	47344 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int i, n, x;
stack<pair<int, int> > S;
vector<int> adj[200005];
int pos[200005][2];
int rmv[200005];
int h[200005];
int up[200005][22];
int val[200005][22];
int curr[200005];

void dfs(int x) {
  for (int k=1; k <= 21; ++k) up[x][k] = up[up[x][k-1]][k-1];

  if (x != 0) {
    curr[x] = pos[x][1]-pos[x][0];
    val[x][0] = min(curr[x], curr[up[x][0]]);
  }

  if (x != 0) for (int k=1; k <= 21; ++k) val[x][k] = min(val[x][k-1], val[up[x][k-1]][k-1]);
  for (auto y : adj[x]) dfs(y);
}

void init(int N, vector<int> H) {
  n = N;
  for (i=1; i <= n; ++i) h[i] = H[i-1];
  for (i=1; i <= n; ++i) rmv[i] = -1;
  for (i=0; i <= N; ++i) adj[i].clear();
  while (!S.empty()) S.pop();
  S.push(make_pair(INT_MAX, 0));
  up[0][0] = 0;
  curr[0] = INT_MAX;
  for (int k=0; k <= 21; ++k) val[0][k] = INT_MAX;

  for (i=1; i <= n; ++i) {
    while (!S.empty() && S.top().X < h[i]) S.pop();
    adj[S.top().Y].push_back(i);
    up[i][0] = S.top().Y;
    S.push(make_pair(h[i], i));
    pos[i][0] = (int)S.size()-1;
  }

  while (!S.empty()) S.pop();
  S.push(make_pair(INT_MAX, 0));

  for (i=n; i >= 1; --i) {
    while (!S.empty() && S.top().X < h[i]) {
      rmv[S.top().Y] = i;
      S.pop();
    }

    S.push(make_pair(h[i], i));
    pos[i][1] = (int)S.size()-1;
  }

  dfs(0);
}

int minimum_jumps(int A, int B, int C, int D) {
  ++A;
  ++B;
  ++C;
  ++D;

  if (A <= rmv[C]) return -1;
  int ans = pos[B][1]-pos[B][0];

  for (int k=21; k >= 0; --k) {
    if (up[A][k] > 0 && up[A][k] > rmv[C]) {
      ans = min(ans, val[A][k]);
      A = up[A][k];
    }
  }

  return pos[B][0]+ans-pos[C][1];
}

• Subtask 1: 4 / 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