oj.uz

Submission #476810

# Submission time Handle Problem Language Result Execution time Memory
476810 2021-09-28T14:55:42 Z Everifall Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1246 ms 52764 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 16;
const int MLOG = 21;
int arr[MAXN],spRight[MLOG][MAXN],spLeft[MLOG][MAXN],spBest[MLOG][MAXN];

void init(int N,vector<int> H){
  arr[0] = arr[N+1] = N+8;
  for(int i=1;i<=N;i++){
    arr[i] = H[i-1];
  }
  stack<int> stkRight,stkLeft;
  for(int i=0;i<=N+1;i++){
    while((!stkRight.empty()) && arr[stkRight.top()] <= arr[i]){
      spRight[0][stkRight.top()] = i;
      stkRight.pop();
    }
    stkRight.push(i);
  }
  spRight[0][N+1] = N+1;
  for(int i=N+1;i>=0;i--){
    while((!stkLeft.empty()) && arr[stkLeft.top()] <= arr[i]){
      spLeft[0][stkLeft.top()] = i;
      stkLeft.pop();
    }
    stkLeft.push(i);
  }
  spLeft[0][0] = 0;
  for(int i=0;i<=N+1;i++){
    if(arr[spLeft[0][i]] > arr[spRight[0][i]]){
      spBest[0][i] = spLeft[0][i];
    }else{
      spBest[0][i] = spRight[0][i];
    }
  }
  for(int i=1;i<MLOG;i++){
    for(int j=0;j<=N+1;j++){
      spLeft[i][j] = spLeft[i-1][spLeft[i-1][j]];
      spRight[i][j] = spRight[i-1][spRight[i-1][j]];
      spBest[i][j] = spBest[i-1][spBest[i-1][j]];
    }
  }
}

int minRight(int idx,int C,int D){
  int res = 1;
  for(int i=MLOG;i>0;i--){
    if(spRight[i-1][idx] < C){
      idx = spRight[i-1][idx];
      res += (1 << (i-1));
    }
  }
  idx = spRight[0][idx];
  return (idx > D ? -1 : res);
}

int minimum_jumps(int A,int B,int C,int D){
  A++,B++,C++,D++;
  int curr = B;
  for(int i=MLOG;i>0;i--){
    if(spLeft[i-1][curr] >= A && spRight[0][spLeft[i-1][curr]] <= D){
      curr = spLeft[i-1][curr];
    }
  }
  int spSum = 0;
  for(int i=MLOG;i>0;i--){
    if(spRight[0][spBest[i-1][curr]] < C){
      curr = spLeft[i-1][curr];
      spSum += (1 << (i-1));
    }
  }
  int res = MAXN;
  if(minRight(curr,C,D) != -1){
    res = min(res,minRight(curr,C,D)+spSum);
  }
  curr = spBest[0][curr];
  if(minRight(curr,C,D) != -1){
    res = min(res,minRight(curr,C,D)+spSum+1);
  }
  return (res == MAXN ? -1 : res);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 170 ms 42304 KB Output is correct
4 Correct 1246 ms 52672 KB Output is correct
5 Correct 1120 ms 26944 KB Output is correct
6 Correct 853 ms 52764 KB Output is correct
7 Correct 924 ms 36416 KB Output is correct
8 Correct 1208 ms 52672 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 0 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 53 ms 42008 KB Output is correct
6 Correct 58 ms 51904 KB Output is correct
7 Correct 37 ms 26924 KB Output is correct
8 Correct 72 ms 51852 KB Output is correct
9 Correct 10 ms 8360 KB Output is correct
10 Correct 61 ms 51864 KB Output is correct
11 Correct 56 ms 52672 KB Output is correct
12 Correct 61 ms 52644 KB Output is correct
13 Correct 66 ms 52508 KB Output is correct
14 Correct 65 ms 51908 KB Output is correct
15 Incorrect 52 ms 52276 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 328 ms 24128 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 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 170 ms 42304 KB Output is correct
4 Correct 1246 ms 52672 KB Output is correct
5 Correct 1120 ms 26944 KB Output is correct
6 Correct 853 ms 52764 KB Output is correct
7 Correct 924 ms 36416 KB Output is correct
8 Correct 1208 ms 52672 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 1 ms 584 KB Output is correct
12 Correct 0 ms 584 KB Output is correct
13 Correct 2 ms 584 KB Output is correct
14 Incorrect 3 ms 584 KB Output isn't correct
15 Halted 0 ms 0 KB -