oj.uz

Submission #530641

# Submission time Handle Problem Language Result Execution time Memory
530641 2022-02-26T05:57:32 Z czhang2718 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1524 ms 59776 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 h[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){
      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 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 265 ms 47640 KB Output is correct
4 Correct 1524 ms 59732 KB Output is correct
5 Correct 914 ms 30180 KB Output is correct
6 Correct 1303 ms 59768 KB Output is correct
7 Correct 1054 ms 40876 KB Output is correct
8 Correct 1351 ms 59760 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 248 KB Output is correct
5 Correct 149 ms 48176 KB Output is correct
6 Correct 202 ms 59756 KB Output is correct
7 Correct 83 ms 30772 KB Output is correct
8 Correct 179 ms 59776 KB Output is correct
9 Correct 19 ms 9236 KB Output is correct
10 Correct 183 ms 59696 KB Output is correct
11 Correct 158 ms 59776 KB Output is correct
12 Correct 177 ms 59752 KB Output is correct
13 Correct 177 ms 59688 KB Output is correct
14 Correct 193 ms 59696 KB Output is correct
15 Correct 236 ms 59652 KB Output is correct
16 Correct 186 ms 59720 KB Output is correct
17 Correct 201 ms 59668 KB Output is correct
18 Correct 0 ms 328 KB Output is correct
19 Correct 0 ms 328 KB Output is correct
20 Incorrect 0 ms 328 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Incorrect 271 ms 27524 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 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Incorrect 271 ms 27524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 265 ms 47640 KB Output is correct
4 Correct 1524 ms 59732 KB Output is correct
5 Correct 914 ms 30180 KB Output is correct
6 Correct 1303 ms 59768 KB Output is correct
7 Correct 1054 ms 40876 KB Output is correct
8 Correct 1351 ms 59760 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 0 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Incorrect 2 ms 328 KB Output isn't correct
14 Halted 0 ms 0 KB -