Submission #1201175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201175		dosts	Rainforest Jumps (APIO21_jumps)	C++20	4 / 100	508 ms	47468 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;
const int N = 2e5+1;
struct ST {
  vector<pii> t;
  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(N);

int up[N][20];

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

int32_t minimum_jumps(int32_t A, int32_t B, int32_t C, int32_t D) {
  A++,B++,C++,D++;
  pii p1 = st.query(1,1,n,A,B);
  pii p2 = st.query(1,1,n,C,D);
  if (up[B][0] > D || up[B][0] == B) return -1;
  if (B == C-1) return 1;
  pii p3 = st.query(1,1,n,B+1,C-1);
  if (p3.ff > p2.ff) return -1;
  if (p3.ff < p1.ff) return 1;
  int p = p1.ss;
  int pp = p;
  for (int i = 19;i>=0;i--) {
    if (up[p][i] < C) {
      p = up[p][i];
    }
  }
  if (up[p][0] > D || up[p][0] == p) return -1;
  return p-pp+1;
}

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