Submission #1191444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191444		emad234	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	3442 ms	56500 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 4e5 + 5;
using namespace std;
int st0[mxN][32],st1[mxN][32];
pii seg[1000005];
int NN;
pii query(int l,int r,int ind,int s,int e){
  if(l > e || r < s) return {0,0};
  if(l >= s && r <= e) return seg[ind];
  int md = (l + r) / 2;
  return max(query(l,md,ind * 2,s,e),query(md + 1,r,ind * 2 + 1,s,e));
}
vector<int>h;
int find(int l,int r,int val,bool sd){
  // if(l == 19) cout<<l<<' '<<r<<'\n';
  if(l > r || query(1,NN,1,l,r).F < val) return -1;
  if(l == r) return query(1,NN,1,l,r).S;
  int md = (l + r) / 2;
  auto a = query(1,NN,1,l,md), b = query(1,NN,1,md + 1,r);
  if (sd){
    if(a.F > val) return find(l,md,val,sd);
    return find(md + 1,r,val,sd);
  }else{
    if(b.F > val) return find(md + 1,r,val,sd);
    return find(l,md,val,sd);
  }
}
int solve(int x,int val,int C,int D){
  int ans = 0;
  for(int i = 20;i >= 0;i--){
    if(h[st1[x][i]] < val){
      x = st1[x][i];
      ans += (1 << i);
      // cout<<i<<' '<<x<<' '<<ans<<'\n';
    }
  }
  if(h[st1[x][0]] == val) return ans + 1;
  // cout<<st1[x][0]<<' '<<C<<' '<<D<<'\n';
  for(int i = 20;i >= 0;i--){
    if(h[st0[x][i]] < val){
      x = st0[x][i];
      ans += (1 << i);
    }
  }
  ans++;
  return {ans};
}
void init(int N, vector<int> H) {
  NN = exp2(ceil(log2(N)));
  for(int i = 0;i < N;i++){
    seg[i + NN] = {H[i],i};
  }
  h = H;
  for(int i = NN - 1;i;i--) seg[i] = max(seg[i * 2],seg[i * 2 + 1]);
  for(int i = 0;i < N;i++){
    int a = find(1,i,H[i],0),b = find(i + 2,N,H[i],1);
    // cout<<i<<' '<<a<<' '<<b<<'\n';
    if(a < b) swap(a,b);
    if(a == -1) a = i;
    if(b == -1) b = i;
    st1[i][0] = a;
    st0[i][0] = b;
  }
  for(int pw = 1;pw <= 20;pw++){
    for(int i = 0;i < N;i++){
      st1[i][pw] = st1[st1[i][pw - 1]][pw - 1];
      st0[i][pw] = st0[st0[i][pw - 1]][pw - 1];
      // cout<<st1[i][pw]<<' ';
    }
    // cout<<'\n';
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  A++;
  B++;
  C++;
  D++;
  if(A != B || C != D) assert(1);
  int mxA = query(1,NN,1,A,B).F,mxidA = query(1,NN,1,A,B).S,mxC = query(1,NN,1,C,D).F,mxidC = query(1,NN,1,C,D).S;
  // // cout<<mxA<<' '<<mxidA<<' '<<mxC<<' '<<mxidC<<'\n';
  if(query(1,NN,1,B,C - 1).F > mxC) return -1;
  int x;
  if(mxC > mxA) x = mxidA;
  else{
    x = find(A,B,mxC,0);
    x = query(1,NN,1,x + 1,B).S;
  }
  return solve(x,mxC,C - 1,D - 1);
}
// 20 3
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
// 0 0 6 6
// 3 4 5 6
// 2 2 5 6

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