oj.uz

Submission #980548

# Submission time Handle Problem Language Result Execution time Memory
980548 2024-05-12T08:35:31 Z vjudge1 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 667 ms 18260 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

vector<int> mq, a;
vector<vector<int>> rm;
vector<int> lt, rt;
int n;
bool sub1 = 1;

void build(){
  rm.resize(mq[n] + 1);
  rm[0] = a;
  for (int q = 1; (1 << q) <= n; q++){
    rm[q].resize(n - (1 << q) + 1);
    for (int i = 0; i < n - (1 << q) + 1; i++)
      rm[q][i] = max(rm[q - 1][i], rm[q - 1][i + (1 << (q - 1))]);
  }
}

void init(int N, vector<int> h) {
  for(int i = 0; i < n; i ++)
    if(h[i] != i + 1)
      sub1 = 0;
  a = h;
  n = N;
  mq.resize(n + 2);
  for(int i = 2; i < n + 2; i ++)
    mq[i] = mq[i / 2] + 1; 
  build();
  lt.resize(n);
  rt.resize(n);
  for(int i = 0; i < n; i ++){
    int l = -1, r = i - 1;
    while(l < r){
      int mid = (l + r + 1) >> 1;
      if(max(rm[mq[i - mid]][mid], rm[mq[i - mid]][i + 1 - (1 << mq[i - mid])]) > a[i])
        l = mid;
      else
        r = mid - 1;
    }
    lt[i] = l;
    l = i + 1, r = n;
    while(l < r){
      int mid = (l + r) >> 1;
      if(max(rm[mq[mid - i]][i], rm[mq[mid - i]][mid + 1 - (1 << mq[mid - i])]) > a[i])
        r = mid;
      else
        l = mid + 1;
    }
    rt[i] = r;
  }
}

int minimum_jumps(int A, int B, int C, int D){
  if(sub1)
    return C - B;
  int ans = 1e9, cnt = 0;
  int index = A;
  while(index < C){
    if(rt[index] == n or rt[index] > D)
      break;
    if(C <= rt[index] and rt[index] <= D){
      ans = min(ans, cnt + 1);
      break;
    }
    if(lt[index] != -1 and rt[lt[index]] != n and rt[rt[index]] < rt[lt[index]] and rt[lt[index]] <= D)
      cnt ++, index = lt[index];
    else{
      cnt ++;
      index = rt[index];
    }
    if (A <= index and index <= B)
      cnt = 0;
  }
  index = B;
  cnt = 0;
  while(index < C){
    if (rt[index] == n or rt[index] > D)
      break;
    if (C <= rt[index] and rt[index] <= D){
      ans = min(ans, cnt + 1);
      break;
    }
    if (lt[index] != -1 and rt[lt[index]] != n and rt[rt[index]] < rt[lt[index]] and rt[lt[index]] <= D)
      cnt++, index = lt[index];
    else
    {
      cnt++;
      index = rt[index];
    }
    if (A <= index and index <= B)
      cnt = 0;
  }
  if(ans == 1e9)
    return -1;
  return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 107 ms 14372 KB Output is correct
4 Correct 623 ms 18260 KB Output is correct
5 Correct 546 ms 9028 KB Output is correct
6 Correct 667 ms 18256 KB Output is correct
7 Correct 512 ms 12120 KB Output is correct
8 Correct 636 ms 18112 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 107 ms 14372 KB Output is correct
4 Correct 623 ms 18260 KB Output is correct
5 Correct 546 ms 9028 KB Output is correct
6 Correct 667 ms 18256 KB Output is correct
7 Correct 512 ms 12120 KB Output is correct
8 Correct 636 ms 18112 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -