제출 #948521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948521		vjudge1	밀림 점프 (APIO21_jumps)	C++17	21 / 100	606 ms	1048576 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;

void init(int N, std::vector<int> H) {
  n = N, h = H;
  l.resize(n), r.resize(n), d.resize(n);
  iota(all(l), 0ll), iota(all(r), 0ll);
  for (int i = 0; i < n; ++i) {
    d[i].assign(n, inf);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i - 1; j >= 0; --j) {
      if (h[i] < h[j]) {
        l[i] = j;
        break;
      }
    }
    for (int j = i + 1; j < n; ++j) {
      if (h[i] < h[j]) {
        r[i] = j;
        break;
      }
    }
  }
  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 {
    return C - B;
  }
}

• 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