Submission #960654

#	Time	Username	Problem	Language	Result	Execution time	Memory
960654		Trisanu_Das	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	907 ms	56168 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;

int mod = 1e9 + 7;
int maxn = 1e8 + 5;
int nnn = 1048590;
int inf = numeric_limits<int>::max()-1;

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dxx[]={0,1,0,-1,1,1,-1,-1};
int dyy[]={1,0,-1,0,1,-1,1,-1};

const int N = 2e5 + 5;
int a[N], n, p[N];
int lft[N] , rght[N];
int par[N][20], L[N][20], R[N][20];

struct seg_tree{

  struct typo{
    int mx;
    void setup(int _sum){
      mx = _sum;
    }
  };

  vector < typo > b;
  int n;

  void init(int l, int r, int node){
    b[node].setup(a[l]);
    return;
  }

  typo merge(typo a, typo b){
    typo c;
    c.mx = max(a.mx, b.mx);
    return c;
  }

  void build(int l, int r, int node){
    if(l == r){
      init(l,r,node);
      return;
    }
    int mid = (l + r)/2;
    int n1 = 2*node;
    int n2 = n1 + 1;
    build(l, mid , n1);
    build(mid+1, r, n2);
    b[node] = merge(b[n1] , b[n2]);
    return;
  }

  void build(int _n){
    n = _n;
    b.resize(4*n);
    build(1,n,1);
  }
  typo get(int l, int r, int node, int x, int y){
    if(y < l || x > r) return {0};
    if(x <= l && y >= r){
      return b[node];
    }
    int mid = (l + r)/2;
    int n1 = 2*node;
    int n2 = n1 + 1;
    return merge(get(l , mid , n1 , x , y) , get(mid + 1, r , n2 , x , y));
  }

  int get(int l, int r){
    return get(1,n,1,l,r).mx;
  } 
}T;

void init(int _n, std::vector<int> H) {
  n = _n;
  for(int i = 1; i <= n; i++){
    a[i] = H[i - 1];
    p[a[i]] = i;
  }
  a[0] = a[n + 1] = n + 1;
  stack < int > st;
  st.push(0);
  for(int i = 1; i <= n; i++){
    while(st.size() && a[st.top()] < a[i]) st.pop();
    lft[i] = st.top();
    st.push(i);
  }
  while(st.size()) st.pop(); 
  st.push(n + 1);
  for(int i = n; i >= 1; i--){
    while(st.size() && a[st.top()] < a[i]) st.pop();
    rght[i] = st.top();
    st.push(i);
  }
  for(int i = 0; i < 20; i++){
    par[0][i] = L[0][i] = R[0][i] = 0;
    par[n+1][i] = L[n+1][i] = R[n+1][i] = n+1;
  }
  for(int i = 1; i <= n; i++){
    if(a[lft[i]] > a[rght[i]]) par[i][0] = lft[i];
    else par[i][0] = rght[i];
    L[i][0] = lft[i];
    R[i][0] = rght[i];
  }
  for(int j = 1; j < 20; j++){
    for(int i = 1; i <= n; i++){
      par[i][j] = par[par[i][j - 1]][j - 1];
      L[i][j] = L[L[i][j-1]][j-1];
      R[i][j] = R[R[i][j-1]][j-1];
    }
  }
  T.build(n);

  return;
}

int apply(int x, int C, int D){
  int res = 0;
  for(int i = 19; i >= 0; i--){
    if(R[x][i] < C) x = R[x][i], res += (1 << i);
  }
  if(rght[x] <= D) res++;
  else res = 1e9;
  return res;
}

int minimum_jumps(int A, int B, int C, int D) {
  A++; B++; C++; D++;

  int e = T.get(C,D);
  if(a[B] > e) return -1;
  int x = B;
  for(int i = 19; i >= 0; i--){
    if(A <= L[x][i] && a[L[x][i]] < e) x = L[x][i];
  }

  int prob = T.get(x, C-1);
  if(prob > e) return -1;
  int ans = 0;
  for(int i = 19; i >= 0; i--){
    if(a[par[x][i]] <= prob){
      ans += (1 << i);
      x = par[x][i];
    }
  }
  int k = apply(x, C, D);
  if(lft[x]) k = min(k, 1 + apply(lft[x], C,D));
  if(k > n) return -1;
  return ans + k;
}

• 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