oj.uz

Submission #530638

# Submission time Handle Problem Language Result Execution time Memory
530638 2022-02-26T05:41:05 Z czhang2718 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1340 ms 59792 KB 
#include "jumps.h"
// #include <bits/stdc++.h>
#include <vector>
using namespace std;

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define f first
#define s second

const int N=200001, LG=18;

int lg[N];
int go[N][LG], goleft[N][LG], goright[N][LG];
int mx[N][LG];
int pos[N];
int n;

int get_max(int l, int r){
  if(r<l) return 0;
  int len=lg[r-l+1];
  return max(mx[l][len], mx[r-(1<<len)+1][len]);
}

void init(int nn, std::vector<int> H) {
  n=nn;
  rep(i,2,n){
    lg[i]=lg[i/2]+1;
  }
  rep(i,0,n-1){
    mx[i][0]=H[i];
    pos[H[i]]=i;
  }
  rep(j,1,lg[n]){
    rep(i,0,n-(1<<j)+1){
      mx[i][j]=max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
    }
  }
  rep(i,0,n-1){
    int ind=i;
    for(int j=lg[n]; j>=0; j--){
      if(ind-(1<<j)>=0 && get_max(ind-(1<<j), i)==H[i]) ind-=(1<<j);
    }
    goleft[i][0]=(ind==0?-1:H[ind-1]);
  }
  rep(i,0,n-1){
    int ind=i;
    for(int j=lg[n]; j>=0; j--){
      if(ind+(1<<j)<n && get_max(i, ind+(1<<j))==H[i]) ind+=(1<<j);
    }
    goright[i][0]=(ind==n-1?-1:H[ind+1]);
  }
  rep(i,0,n-1){
    go[i][0]=max(goleft[i][0], goright[i][0]);
  }
  rep(j,1,lg[n]){
    rep(i,0,n-(1<<j)+1){
      goleft[i][j]=(goleft[i][j-1]==-1?-1:goleft[pos[goleft[i][j-1]]][j-1]);
      goright[i][j]=(goright[i][j-1]==n?n:goright[pos[goright[i][j-1]]][j-1]);
      go[i][j]=(go[i][j-1]==-1?-1:go[pos[go[i][j-1]]][j-1]);
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  int mx=get_max(C, D);
  if(get_max(B, C)>mx) return -1;

  for(int j=lg[n]; j>=0; j--){
    if(A+(1<<j)<=B && get_max(A+(1<<j), B)>mx) A+=(1<<j);
  }
  // if(A==B) return -1;
  if(get_max(A, B)>mx) A++;

  int ans=0;
  int a=pos[get_max(A, B)];
  int y=get_max(B+1, C-1);
  for(int j=lg[n]; j>=0; j--){
    if(go[a][j]>0 && go[a][j]<=y) ans+=(1<<j), a=pos[go[a][j]];
  }
  if(goright[a][0]!=-1 && pos[goright[a][0]]>=C) return ans+1;
  if(goleft[a][0]!=-1 && goleft[a][0]<mx && goleft[a][0]>y) return ans+2;
  for(int j=lg[n]; j>=0; j--){
    if(goright[a][j]>0 && pos[goright[a][j]]<C) ans+=(1<<j), a=pos[goright[a][j]];
  }
  return ans+1;
}
//

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 266 ms 47520 KB Output is correct
4 Correct 1262 ms 59740 KB Output is correct
5 Correct 1012 ms 30252 KB Output is correct
6 Correct 1275 ms 59680 KB Output is correct
7 Correct 989 ms 40840 KB Output is correct
8 Correct 1340 ms 59740 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 3 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 3 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 137 ms 48096 KB Output is correct
6 Correct 202 ms 59688 KB Output is correct
7 Correct 88 ms 30748 KB Output is correct
8 Correct 180 ms 59748 KB Output is correct
9 Correct 17 ms 9176 KB Output is correct
10 Correct 180 ms 59732 KB Output is correct
11 Correct 162 ms 59792 KB Output is correct
12 Incorrect 164 ms 59716 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 247 ms 27448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 247 ms 27448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 266 ms 47520 KB Output is correct
4 Correct 1262 ms 59740 KB Output is correct
5 Correct 1012 ms 30252 KB Output is correct
6 Correct 1275 ms 59680 KB Output is correct
7 Correct 989 ms 40840 KB Output is correct
8 Correct 1340 ms 59740 KB Output is correct
9 Correct 0 ms 200 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 0 ms 200 KB Output is correct
13 Incorrect 3 ms 200 KB Output isn't correct
14 Halted 0 ms 0 KB -