Submission #678936

#	Time	Username	Problem	Language	Result	Execution time	Memory
678936		cig32	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1483 ms	53796 KiB

jumps

#include "jumps.h"
#include <stack>
#include <vector>
#include <iostream>
#include <queue>
 
const int MAXN = 200010;
 
int L[MAXN], R[MAXN];
int N_;
int mi[19][MAXN], ma[19][MAXN], rr[19][MAXN];
bool st1;
int V[MAXN];

std::pair<int, int> str[4 * MAXN];

void u(int l, int r, int tar, int idx, int val) {
  if(l == r) {
    str[idx] = {val, tar}; return;
  }
  int mid = (l + r) >> 1;
  if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
  else u(mid+1, r, tar, 2*idx+2, val);
  str[idx] = max(str[2*idx+1], str[2*idx+2]);
}

std::pair<int, int> qu1(int l, int r, int constl, int constr, int idx) {
  if(l<=constl && constr<=r) return str[idx];
  int mid = (constl+constr) >> 1;
  if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2);
  else if(constr < l || r < mid+1) return qu1(l, r, constl, mid, 2*idx+1);
  else return max(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
}

int qu2(int l, int r, int constl, int constr, int idx, int val) {
  if(l<=constl && constr<=r) {
    if(str[idx].first <= val) {
      return -1;
    }
    while(constl < constr) {
      int mid = (constl + constr) >> 1;
      if(str[2*idx+2].first > val) constl = mid + 1, idx = 2 * idx + 2;
      else constr = mid, idx = 2 * idx + 1;
    }
    return constl;
  }
  int mid = (constl+constr) >> 1;
  if(mid<l || r< constl) return qu2(l, r, mid+1, constr, 2*idx+2, val);
  else if(constr< l || r< mid+1) return qu2(l, r, constl, mid, 2*idx+1, val);
  else {
    int res = qu2(l, r, mid+1, constr, 2*idx+2, val);
    if(res != -1) return res;
    return qu2(l, r, constl, mid, 2*idx+1, val);
  }
}

void update(int i, int v) {
  u(0, N_ - 1, i, 0, v);
}

int query_max(int l, int r) {
  return qu1(l, r, 0, N_ - 1, 0).second;
}

int last_greater(int l, int r, int c) {
  return qu2(l, r, 0, N_ - 1, 0, c);
}
 
void init(int N, std::vector<int> H) {
  N_ = N;
  for(int i=0; i<N; i++) update(i, H[i]);
  st1 = 1;
  for(int i=0; i<N; i++) {
    L[i] = R[i] = -1;
    V[i] = H[i];
    if(H[i] != i + 1) st1 = 0;
  }
  std::stack<int> st;
  for(int i=0; i<N; i++) {
    while(st.size() && H[st.top()] < H[i]) {
      st.pop();
    }
    if(st.size()) L[i] = st.top();
    st.push(i);
  }
  while(st.size()) st.pop();
  for(int i=N-1; i>=0; i--) {
    while(st.size() && H[st.top()] < H[i]) {
      st.pop();
    }
    if(st.size()) R[i] = st.top();
    st.push(i);
  }
  while(st.size()) st.pop();
  for(int i=0; i<N; i++) {
    rr[0][i] = R[i];
  }
  for(int i=0; i<N; i++) {
    if(L[i] == -1 && R[i] == -1) {
      mi[0][i] = ma[0][i] = -1;
    }
    else if(L[i] == -1) {
      mi[0][i] = ma[0][i] = R[i];
    }
    else if(R[i] == -1) {
      mi[0][i] = ma[0][i] = L[i];
    }
    else {
      mi[0][i] = (H[L[i]] < H[R[i]] ? L[i] : R[i]);
      ma[0][i] = (H[L[i]] > H[R[i]] ? L[i] : R[i]);
    }
  }
  for(int i=1; i<19; i++) {
    for(int j=0; j<N; j++) {
      if(mi[i-1][j] == -1) mi[i][j] = -1;
      else mi[i][j] = mi[i-1][mi[i-1][j]];
      if(ma[i-1][j] == -1) ma[i][j] = -1;
      else ma[i][j] = ma[i-1][ma[i-1][j]];
      if(rr[i-1][j] == -1) rr[i][j] = -1;
      else rr[i][j] = rr[i-1][rr[i-1][j]];
    }
  }
  
}
int qcnt = 0;
int minimum_jumps(int A, int B, int C, int D) {
  if(V[query_max(B, C - 1)] > V[query_max(C, D)]) return -1;
  int lg = last_greater(A, B, V[query_max(C, D)]);
  if(lg == -1) lg = A - 1;
  A = query_max(lg+1, B);
  //std::cout << A << " !!! ";
  int X = V[query_max(B, C - 1)];
  int Y = V[query_max(C, D)];
  int ans = 0;
  //std::cout << X << " " << Y << " ";
  for(int i=18; i>=0; i--) {
    if(ma[i][A] != -1) {
      if(V[ma[i][A]] < X) {
        ans += (1 << i);
        A = ma[i][A];
      }
    }
  }
  if(C <= rr[0][A] && rr[0][A] <= D) return ans + 1;
  if(ma[0][A] != -1 && X <= V[ma[0][A]] && V[ma[0][A]] < Y) {
    return ans + 2;
  }
  
  int lb = 0, rb = (1 << 19) - 1;
  while(lb < rb) {
    int mid = (lb + rb) >> 1;
    bool ok = 1;
    int sto = A;
    for(int i=18; i>=0; i--) {
      if(!(mid & (1 << i))) continue;
      if(rr[i][sto] != -1) {
        if(V[rr[i][sto]] <= Y) {
          sto = rr[i][sto];
        }
      }
      else {
        ok = 0; break;
      }
    }
    //std::cout << "Steps " << mid << " res " << sto << " flag " << ok << "\n";
    if(C <= sto || !ok)rb = mid;
    else lb = mid+ 1;
  }
  if(rb != (1 << 19) - 1) return ans+ lb;
  return -1;
}

• 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