oj.uz

답안 #530637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530637 2022-02-26T05:40:04 Z czhang2718 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1410 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 264 ms 47632 KB Output is correct
4 Correct 1320 ms 59680 KB Output is correct
5 Correct 1081 ms 30248 KB Output is correct
6 Correct 1370 ms 59708 KB Output is correct
7 Correct 985 ms 40840 KB Output is correct
8 Correct 1410 ms 59696 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 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 1 ms 200 KB Output is correct
5 Incorrect 1 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 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 1 ms 200 KB Output is correct
5 Incorrect 1 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 260 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 138 ms 48116 KB Output is correct
6 Correct 218 ms 59764 KB Output is correct
7 Correct 81 ms 30656 KB Output is correct
8 Correct 191 ms 59660 KB Output is correct
9 Correct 17 ms 9160 KB Output is correct
10 Correct 185 ms 59776 KB Output is correct
11 Correct 155 ms 59712 KB Output is correct
12 Incorrect 184 ms 59760 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 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 285 ms 27404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 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 285 ms 27404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 264 ms 47632 KB Output is correct
4 Correct 1320 ms 59680 KB Output is correct
5 Correct 1081 ms 30248 KB Output is correct
6 Correct 1370 ms 59708 KB Output is correct
7 Correct 985 ms 40840 KB Output is correct
8 Correct 1410 ms 59696 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 1 ms 200 KB Output is correct
13 Incorrect 1 ms 200 KB Output isn't correct
14 Halted 0 ms 0 KB -