Submission #1003435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003435		AdamGS	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1652 ms	255172 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;
set<int>S[4*LIM];
int cnt(int l, int r) {
  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 licz(int v, int x) {
  auto it=S[v].lower_bound(x);
  if(it==S[v].begin()) return -1;
  --it;
  auto a=*it;
  return a;
}
int znajdz(int l, int r, int x) {
  l+=N; r+=N;
  int ans=-1;
  ans=max(ans, licz(l, x));
  ans=max(ans, licz(r, x));
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, licz(l+1, x));
    if(r%2==1) ans=max(ans, licz(r-1, x));
    l/=2; r/=2;
  }
  return ans;
}
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];
    S[N+i].insert(T[i]);
    gdzie[T[i]]=i;
  }
  for(int i=N-1; i; --i) {
    tr[i]=max(tr[2*i], tr[2*i+1]);
    for(auto j : S[2*i]) S[i].insert(j);
    for(auto j : S[2*i+1]) S[i].insert(j);
  }
  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) {
    ans+=1<<i;
    x=nxt[x][i];
  }
  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: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19