Submission #804987

#	Time	Username	Problem	Language	Result	Execution time	Memory
804987		radaiosm7	Rainforest Jumps (APIO21_jumps)	C++11	0 / 100	192 ms	37984 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];

void dfs(int x) {
  for (int k=2; k <= 21; ++k) up[x][k] = up[up[x][k-1]][k-1];
  if (x != 0) val[x][0] = pos[x][1]-pos[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;
  while (!S.empty()) S.pop();
  S.push(make_pair(INT_MAX, 0));
  up[0][0] = 0;
  up[0][1] = 0;
  val[0][0] = INT_MAX;

  for (i=1; i <= n; ++i) {
    up[i][0] = i;
    while (!S.empty() && S.top().X < h[i]) S.pop();
    adj[S.top().Y].push_back(i);
    up[i][1] = 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;

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

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

  return (ans == INT_MAX) ? -1 : (pos[B][0]+ans-pos[C][1]);
}

• 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