Submission #804521

#	Time	Username	Problem	Language	Result	Execution time	Memory
804521		radaiosm7	Rainforest Jumps (APIO21_jumps)	C++11	33 / 100	4075 ms	14904 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;
queue<int> Q;
vector<int> adj[200005];
int d[200005];
const int INF = INT_MAX;

void init(int N, vector<int> H) {
  n = N;
  for (i=0; i < N; ++i) {
    while (!S.empty() && S.top().X < H[i]) S.pop();
    if (!S.empty()) adj[i].push_back(S.top().Y);
    S.push(make_pair(H[i], i));
  }

  while (!S.empty()) S.pop();

  for (i=N-1; i >= 0; --i) {
    while (!S.empty() && S.top().X < H[i]) S.pop();
    if (!S.empty()) adj[i].push_back(S.top().Y);
    S.push(make_pair(H[i], i));
  }

}

int minimum_jumps(int A, int B, int C, int D) {
  fill(d, d+n, INF);
  while (!Q.empty()) Q.pop();

  for (i=A; i <= B; ++i) {
    Q.push(i);
    d[i] = 0;
  }

  while (!Q.empty()) {
    x = Q.front();
    Q.pop();

    for (auto y : adj[x]) {
      if (C <= y && y <= D) return d[x]+1;
      if (d[y] == INF) {
        Q.push(y);
        d[y] = d[x]+1;  
      }
    }
  }

  return -1;
}

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