oj.uz

Submission #980532

# Submission time Handle Problem Language Result Execution time Memory
980532 2024-05-12T08:25:06 Z vjudge1 Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 18436 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;

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) {
  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 << 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){
  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);
    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);
    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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2802 ms 14404 KB Output is correct
4 Execution timed out 4026 ms 18124 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.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 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 2 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 2 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 60 ms 14380 KB Output is correct
6 Correct 83 ms 18120 KB Output is correct
7 Correct 36 ms 9028 KB Output is correct
8 Correct 80 ms 18124 KB Output is correct
9 Correct 8 ms 2784 KB Output is correct
10 Correct 80 ms 18112 KB Output is correct
11 Correct 78 ms 18252 KB Output is correct
12 Correct 83 ms 18252 KB Output is correct
13 Correct 76 ms 18112 KB Output is correct
14 Incorrect 71 ms 18260 KB Output isn't correct
15 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 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 169 ms 7944 KB Output is correct
5 Incorrect 738 ms 18436 KB Output isn't correct
6 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 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 169 ms 7944 KB Output is correct
5 Incorrect 738 ms 18436 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2802 ms 14404 KB Output is correct
4 Execution timed out 4026 ms 18124 KB Time limit exceeded
5 Halted 0 ms 0 KB -