oj.uz

Submission #980540

# Submission time Handle Problem Language Result Execution time Memory
980540 2024-05-12T08:28:38 Z vjudge1 Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 18264 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);
      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
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 2399 ms 14376 KB Output is correct
4 Execution timed out 4027 ms 18164 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 1 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 1 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 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 0 ms 344 KB Output is correct
5 Correct 59 ms 14356 KB Output is correct
6 Correct 72 ms 18248 KB Output is correct
7 Correct 37 ms 9140 KB Output is correct
8 Correct 72 ms 18100 KB Output is correct
9 Correct 9 ms 2780 KB Output is correct
10 Correct 80 ms 18096 KB Output is correct
11 Correct 71 ms 18264 KB Output is correct
12 Correct 70 ms 18100 KB Output is correct
13 Correct 71 ms 18120 KB Output is correct
14 Incorrect 71 ms 18112 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 152 ms 8144 KB Output is correct
5 Incorrect 644 ms 18000 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 152 ms 8144 KB Output is correct
5 Incorrect 644 ms 18000 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2399 ms 14376 KB Output is correct
4 Execution timed out 4027 ms 18164 KB Time limit exceeded
5 Halted 0 ms 0 KB -