Submission #980524

#	Time	Username	Problem	Language	Result	Execution time	Memory
980524		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	0 ms	344 KiB

jumps

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

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

vector<int> mq, a;
vector<vector<int>> rm;
vector<int> lt, rt;
int n;

void build(){
  rm.resize(mq[n] + 1);
  rm[0] = a;
  for (int q = 1; (1 << q) <= n; q++){
    rm[q].resize(n - (1 << q) + 1);
    for (int i = 0; i < n - (1 << q) + 1; i++)
      rm[q][i] = max(rm[q - 1][i], rm[q - 1][i + (1 << (q - 1))]);
  }
}

void init(int N, vector<int> h) {
  a = h;
  n = N;
  mq.resize(n + 2);
  for(int i = 2; i < n + 2; i ++)
    mq[i] = mq[i / 2] + 1; 
  build();
  lt.resize(n);
  rt.resize(n);
  for(int i = 0; i < n; i ++){
    int l = -1, r = i - 1;
    while(l < r){
      int mid = (l + r + 1) >> 1;
      if(max(rm[mq[i - mid]][mid], rm[mq[i - mid]][i - (1 << mq[i - mid])]) > a[i])
        l = mid;
      else
        r = mid - 1;
    }
    lt[i] = l;
    l = i + 1, r = n;
    while(l < r){
      int mid = (l + r) >> 1;
      if(max(rm[mq[mid - i]][i], rm[mq[mid - i]][mid + 1 - (1 << mq[mid - i])]) > a[i])
        r = mid;
      else
        l = mid + 1;
    }
    rt[i] = r;
  }
  print(lt)
  print(rt)
}

int minimum_jumps(int A, int B, int C, int D){
  int ans = 1e9, cnt = 0;
  int index = A;
  while(index < C){
    if(rt[index] == n or rt[index] > D)
      break;
    if(C <= rt[index] and rt[index] <= D)
      ans = min(ans, cnt + 1);
    if(lt[index] != -1 and rt[lt[index]] != n and rt[rt[index]] < rt[lt[index]] and rt[lt[index]] <= D)
      cnt ++, index = lt[index];
    else{
      cnt ++;
      index = rt[index];
    }
    if (A <= index and index <= B)
      cnt = 0;
  }
  index = B;
  while(index < C){
    if (rt[index] == n or rt[index] > D)
      break;
    if (C <= rt[index] and rt[index] <= D)
      ans = min(ans, cnt + 1);
    if (lt[index] != -1 and rt[lt[index]] != n and rt[rt[index]] < rt[lt[index]] and rt[lt[index]] <= D)
      cnt++, index = lt[index];
    else
    {
      cnt++;
      index = rt[index];
    }
    if (A <= index and index <= B)
      cnt = 0;
  }
  if(ans == 1e9)
    return -1;
  return ans;
}

• 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