Submission #1201239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201239		dosts	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	4098 ms	25516 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;
struct ST {
  vector<pii> t;
  ST(){};
  ST(int nn) {
    t.assign(4*nn+1,{0,0});
  }
  void update(int node,int l,int r,int p,pii v) {
    if (l == r) {
      t[node] = v;
      return;
    }
    int m = (l+r) >> 1;
    if (p <= m) update(2*node,l,m,p,v);
    else update(2*node+1,m+1,r,p,v);
    t[node] = max(t[2*node],t[2*node+1]);
  }

  pii query(int node,int l,int r,int L,int R) {
    if (l > R || r < L) return {0,0};
    if (l >= L && r <= R) return t[node];
    int m = (l+r) >> 1;
    return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
  }
}st;

int up[200005][20];

int n;
vector<int> hh;
void init(int N, std::vector<int> H) {
  hh = H;
  n = N;
  st = ST(n);
  for (int i=1;i<=N;i++) st.update(1,1,N,i,{H[i-1],i});
  stack<int> stk;
  for (int j = 0;j<20;j++) up[n+1][j] = n+1;
  for (int i = N;i>=1;i--) {
    while (!stk.empty() && H[stk.top()-1] < H[i-1]) stk.pop();
    if (stk.empty()) up[i][0] = n+1;
    else up[i][0] = stk.top();
    stk.push(i);
  }
  for (int i=1;i<20;i++) {
    for (int j = 1;j<=N;j++) up[j][i] = up[up[j][i-1]][i-1];
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  A++,B++,C++,D++;
  assert(A<=B && B<C && C<=D);
  if (up[B][0] > D) return -1;
  if (B == C-1) return 1;
  pii p1 = st.query(1,1,n,A,B);
  pii p2 = st.query(1,1,n,C,D);
  pii p3 = st.query(1,1,n,B+1,C-1);
  if (p3.ff > p2.ff) return -1;
  int select = 0;
  for (int i = B;i>=A;i--) if (up[i][0] >= C && up[i][0] <= D) return 1;
  for (int i = B;i>=A;i--) {
    if (up[i][0] > B && up[i][0] <= D) select = i;
  }
  int p = select;
  int steps = 0;
  for (int i = 19;i>=0;i--) {
    if (up[p][i] < C) {
      steps+=(1<<i);
      p = up[p][i];
    }
  }
  return steps+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