Submission #948537

#	Time	Username	Problem	Language	Result	Execution time	Memory
948537		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4006 ms	141936 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S& a, const T& b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S& a, const T& b) {
	return a < b ? (a = b) == b : false;
}

const int inf = 1e9;

struct segtree {
  int n;
  vector<int> t;
  segtree(int n) {
    this -> n = n;
    t.assign(4 * n + 4, inf);
  }
  void upd(int v, int tl, int tr, int i, int delta) {
    if (tl == tr) {
      t[v] = delta;
      return;
    }
    int tm = (tl + tr) / 2;
    if (tm >= i) upd(2 * v, tl, tm, i, delta);
    else upd(2 * v + 1, tm + 1, tr, i, delta);
    t[v] = min(t[2 * v], t[2 * v + 1]);
  } void upd(int i, int delta) {
    upd(1, 1, n, i, delta);
  }
  int get(int v, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return inf;
    if (tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return min(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
  } int get(int l, int r) {
    return get(1, 1, n, l, r);
  }
};

int n;
vector<int> h, l, r;
vector<vector<int>> d;
vector<segtree> T;
bool increasing = true;

void init(int N, std::vector<int> H) {
  n = N, h = H;
  for (int i = 1; i < n; ++i) {
    if (h[i] <= h[i - 1]) increasing = false;
  }
  l.resize(n), r.resize(n), d.resize(n);
  iota(all(l), 0ll), iota(all(r), 0ll);
  stack<int> stk;
  for (int i = 0; i < n; ++i) {
    while (!stk.empty() && h[stk.top()] <= h[i]) {
      stk.pop();
    }
    if (!stk.empty()) l[i] = stk.top();
    stk.push(i);
  }
  while (!stk.empty()) stk.pop();
  for (int i = n - 1; i >= 0; --i) {
    while (!stk.empty() && h[stk.top()] <= h[i]) {
      stk.pop();
    }
    if (!stk.empty()) r[i] = stk.top();
    stk.push(i);
  }
  if (n <= 2000) {
    for (int i = 0; i < n; ++i) {
      d[i].assign(n, inf);
    }
    vector<segtree> t(n, segtree(n));
    for (int i = 0; i < n; ++i) {
      d[i][i] = 0;
      queue<int> q;
      q.push(i);
      while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (chmin(d[i][l[v]], d[i][v] + 1)) {
          q.push(l[v]);
        }
        if (chmin(d[i][r[v]], d[i][v] + 1)) {
          q.push(r[v]);
        }
      }
      for (int j = 0; j < n; ++j) {
        t[i].upd(j + 1, d[i][j]);
      }
    }
    T = t;
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  if (n <= 2000) {
    int res = inf;
    for (int i = A; i <= B; ++i) {
      chmin(res, T[i].get(C + 1, D + 1));
    }
    return res == inf ? -1 : res;
  } else if (increasing) {
    return C - B;
  } else {
    vector<int> d(n, inf);
    queue<int> q;
    for (int i = A; i <= B; ++i) {
      q.push(i);
      d[i] = 0;
    }
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      if (chmin(d[l[v]], d[v] + 1)) {
        q.push(l[v]);
      }
      if (chmin(d[r[v]], d[v] + 1)) {
        q.push(r[v]);
      }
    }
    int res = inf;
    for (int i = C; i <= D; ++i) {
      chmin(res, d[i]);
    }
    return res == inf ? -1 : res;
  }
}

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