Submission #412312

#	Time	Username	Problem	Language	Result	Execution time	Memory
412312		model_code	Rainforest Jumps (APIO21_jumps)	C++17	21 / 100	4070 ms	1048580 KiB

jumps

#include "jumps.h"

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

class MinSegmentTree {
 private:
  int N;
  vector<int> tree;

  void build(const vector<int> &val, int ix, int L, int R) {
    if (L == R) {
      tree[ix] = val[L];
      return;
    }
    int M = (L + R) >> 1;
    build(val, ix * 2 + 1, L, M);
    build(val, ix * 2 + 2, M + 1, R);
    tree[ix] = min(tree[ix * 2 + 1], tree[ix * 2 + 2]);
  }

  int query(int ix, int L, int R, int x, int y) {
    if (x <= L && R <= y) {
      return tree[ix];
    }
    if (R < x || y < L) {
      return INT_MAX;
    }
    int M = (L + R) >> 1;
    return min(query(ix * 2 + 1, L, M, x, y),
               query(ix * 2 + 2, M + 1, R, x, y));
  }

 public:
  void build(const vector<int> &val) {
    N = val.size();
    tree.resize(4 * N);
    build(val, 0, 0, N - 1);
  }

  int query(int x, int y) {
    return query(0, 0, N - 1, x, y);
  }
};

int N;
vector<MinSegmentTree> seg_trees;

void init(int _N, std::vector<int> H) {
  N = _N;
  seg_trees = vector<MinSegmentTree>(N);

  vector<vector<int>> adj = vector<vector<int>>(N, vector<int>());
  for (int i = 0; i < N; ++i) {
    for (int j = i - 1; j >= 0; --j) {
      if (H[j] > H[i]) {
        adj[i].push_back(j);
        break;
      }
    }
    for (int j = i + 1; j < N; ++j) {
      if (H[j] > H[i]) {
        adj[i].push_back(j);
        break;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    vector<int> dist(N, INT_MAX);
    queue<int> q;

    dist[i] = 0;
    q.push(i);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : adj[u]) {
        if (dist[v] > dist[u] + 1) {
          dist[v] = dist[u] + 1;
          q.push(v);
        }
      }
    }

    seg_trees[i].build(dist);
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  int jumps = INT_MAX;
  for (int s = A; s <= B; ++s) {
    jumps = min(jumps, seg_trees[s].query(C, D));
  }
  return jumps == INT_MAX ? -1 : jumps;
}

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