제출 #980449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
980449		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	146 ms	36292 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ff first
#define ss second
const int mod = 1e9 + 7;
const int inf = 1e9;
const int logn = 20;

template<typename T>
int len(T &a){return a.size();}

vector<int> lef, rig;

vector<vector<int>> up;

int n;
bool sub1 = 1;

struct Segtree{
  vector<pair<int,int>> t;
  int n;
  void init(int _n){
    n = _n;
    t.resize(2 * n);
  }
  pair<int,int> merge(const pair<int,int> &a, const pair<int,int> &b){
    return max(a, b);
  }
  void build(vector<int> &a){
    init(len(a));
    for(int i = 0; i < n; i ++) t[i + n] = {a[i], i};
    for(int i = n - 1; i > 0; i --) t[i] = merge(t[i << 1], t[i << 1 | 1]);
  }

  pair<int,int> get(int l, int r){
    l += n; r += n;
    pair<int,int> res = {0, -1};
    while(l <= r){
      if(l % 2) res = merge(res, t[l ++]);
      if(r % 2 == 0) res = merge(res, t[r --]);
      l /= 2; r /= 2;
    }
    return res;
  }
} t;

vector<int> h;



void init(int N, vector<int> H) {
  h.push_back(inf);
  n = N;
  for(int i = 0; i < n; i ++) h.push_back(H[i]);
  vector<int> st;
  st.push_back(0);
  lef.resize(n + 1), rig.resize(n + 1);
  for(int i = 1; i <= n; i ++){
    if(h[i] != i + 1) sub1 = 0;
    while(h[st.back()] <= h[i]) st.pop_back();
    lef[i] = st.back();
    st.push_back(i);
  }
  // for(auto u : lef) cout << u << ' ';
  // cout << endl;
  if(sub1) return;

  //cout << "done" << endl;
  st = {0};

  for(int i = n; i >= 1; i --){
    while(h[st.back()] <= h[i]) st.pop_back();
    rig[i] = st.back();
    st.push_back(i);
  }

  t.build(h); 
  up.assign(logn, vector<int> (n + 1));
  // it's always optimal to jump higher tree

  for(int i = 1; i <= n; i ++){
    up[0][i] = (h[lef[i]] >= h[rig[i]] ? lef[i] : rig[i]);
  }
  for(int j = 1; j < logn; j ++){
    for(int i = 1; i <= n; i ++){
      up[j][i] = up[j - 1][up[j - 1][i]];
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  if(sub1) return C - B;
  A ++, B ++, C ++, D ++;
  assert(C == D);
  int l = A - 1, r = B + 1;
  while(r - l > 1){
    int m = (l + r) / 2;
    if(t.get(m, C - 1).ff < h[C]){
      r = m;
    }else l = m;
  }
  //cout << t.get(r + 1, C - 1).ff << endl;
  //cout << t.get(r + 1, C - 1);
  if(r == B + 1){
    return -1;
  }
  r = t.get(r, B).ss;
  //cout << r << endl;
  int ans = 0;

  for(int j = logn - 1; j >= 0; j --){
    if(h[up[j][r]] < h[C]) {
      r = up[j][r];
      ans |= 1 << j;
    }
  }
  return ans + 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