oj.uz

Submission #981231

# Submission time Handle Problem Language Result Execution time Memory
981231 2024-05-13T02:39:52 Z Muhammad_Aneeq Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 17024 KB 
#include "jumps.h"

#include <vector>
#include <set>
#include <cmath>
#include <iostream>
using namespace std;
int const N=2e5+10,LG=20;
int mx[N][LG]={};
vector<int>a;
int get(int l,int r)
{
  int lg=log2(r-l+1);
  if (a[mx[l][lg]]>=a[mx[r-(1<<lg)+1][lg]])
    return mx[l][lg];
  return mx[r-(1<<lg)+1][lg];
}
void init(int N,vector<int> H) 
{
  a=H;
  for (int i=0;i<N;i++)
    mx[i][0]=i;
  for (int i=1;(1<<i)<=N;i++)
    for (int j=0;j+(1<<(i-1))<N;j++)
    {
      if (a[mx[j][i-1]]>=a[mx[j+(1<<(i-1))][i-1]])
        mx[j][i]=mx[j][i-1];
      else
        mx[j][i]=mx[j+(1<<(i-1))][i-1];
    }
}
int minimum_jumps(int A, int B, int C, int D) 
{
  int minsteps=1e9+10;
  for (int i=A;i<=B;i++)
  {
    int z=get(i,D);
    if (z>=C&&z<=D)
    {
      int st=i,en=z,cnt=0;;
      while (1)
      {
        int f=st;
        while (st+1<en)
        {
          int mid=(st+en)/2;
          if (get(st,mid)>f)
            en=mid;
          else
            st=mid;
        }
        cnt++;
        if (en>=C&&en<=D)
          break;
        st=en;
        en=z+1;
      }
      minsteps=min(cnt,minsteps);
    }
  }
  if (minsteps==1e9+10)
    return -1;  
  return minsteps;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4066 ms 14540 KB Time limit exceeded
4 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 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 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 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 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 Execution timed out 4059 ms 17024 KB Time limit exceeded
6 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 Incorrect 126 ms 9772 KB Output isn't correct
5 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 Incorrect 126 ms 9772 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4066 ms 14540 KB Time limit exceeded
4 Halted 0 ms 0 KB -