Submission #1003455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003455		AdamGS	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1037 ms	40016 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, LG=20;
int tr[4*LIM], lewo[LIM], prawo[LIM], nxtr[LIM][LG], nxt[LIM][LG], T[LIM], gdzie[LIM], n, N=1;
int cnt(int l, int r) {
  if(l>r) return -1;
  l+=N; r+=N;
  int ans=max(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, tr[l+1]);
    if(r%2==1) ans=max(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
int znajdz(int l, int r, int x) {
  int po=l, ko=r+1;
  while(po<ko) {
    int sr=(po+ko)/2;
    if(cnt(sr, r)<x) ko=sr; else po=sr+1;
  }
  return cnt(po, r);
}
void init(int _n, vector<int>_T) {
  n=_n;
  while(N<n) N*=2;
  rep(i, n) T[i]=_T[i]-1;
  rep(i, n) {
    tr[N+i]=T[i];
    gdzie[T[i]]=i;
  }
  for(int i=N-1; i; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
  vector<int>V;
  rep(i, n) {
    while(V.size()>0 && T[V.back()]<T[i]) V.pop_back();
    if(V.size()) lewo[i]=V.back(); else lewo[i]=i;
    V.pb(i);
  }
  V.clear();
  for(int i=n-1; i>=0; --i) {
    while(V.size()>0 && T[V.back()]<T[i]) V.pop_back();
    if(V.size()) prawo[i]=V.back(); else prawo[i]=i;
    V.pb(i);
  }
  rep(i, n) nxtr[i][0]=nxt[i][0]=prawo[i];
  rep(i, n) if(T[lewo[i]]>T[prawo[i]]) nxt[i][0]=lewo[i];
  for(int j=1; j<LG; ++j) {
    rep(i, n) {
      nxt[i][j]=nxt[nxt[i][j-1]][j-1];
      nxtr[i][j]=nxtr[nxtr[i][j-1]][j-1];
    }
  }
}
int minimum_jumps(int a, int b, int c, int d) {
  int p=znajdz(a, b, cnt(c, d));
  if(p==-1) return -1;
  int x=gdzie[p];
  if(cnt(x, c-1)>cnt(c, d)) return -1;
  if(nxtr[x][0]>=c) return 1;
  int ans=1;
  for(int i=LG-1; i>=0; --i) if(nxtr[nxt[x][i]][0]<c && nxtr[nxt[x][i]][0]!=nxt[x][i]) {
    ans+=1<<i;
    x=nxt[x][i];
  }
  if(nxtr[nxt[x][0]][0]<=d && nxtr[nxt[x][0]][0]!=nxt[x][0]) {
    x=nxt[x][0];
    ++ans;
  }
  for(int i=LG-1; i>=0; --i) if(nxtr[x][i]<c) {
    ans+=1<<i;
    x=nxtr[x][i];
  }
  return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19