oj.uz

Submission #981269

# Submission time Handle Problem Language Result Execution time Memory
981269 2024-05-13T03:20:02 Z Muhammad_Aneeq Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 8920 KB 
#include "jumps.h"

#include <vector>
#include <set>
#include <cmath>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int const N=2e5+10,LG=20;
int mx[N][LG]={};
int nextmx[N]={};
bool vis[N]={};
vector<vector<int>>ans;
int ind[N]={};
void init(int N,vector<int> H) 
{
  deque<int>d;
  for (int i=0;i<N;i++)
  {
    nextmx[i]=-1;
    if (d.empty())
    {
      d.push_front(i);
      continue;
    }
    while (d.size()&&H[d.front()]<H[i])
    {
      nextmx[d.front()]=i;
      d.pop_front();
    }
    d.push_front(i);
  }
  for (int i=0;i<N;i++)
  {
    if (!vis[i])
    {
      int z=i;
      vis[z]=1;
      ans.push_back({z});
      ind[z]=ans.size()-1;
      while (nextmx[z]!=-1&&!vis[nextmx[z]])
      {
        z=nextmx[z];
        vis[z]=1;
        ans.back().push_back(z);
      } 
    }
  }
}
int minimum_jumps(int A, int B, int C, int D) 
{
  int minsteps=1e9+10;
  for (int i=A;i<=B;i++)
  {
    int z=i;
    int cnt=0;
    while (ans[ind[z]].back()<C)
    {
      cnt+=ans[ind[z]].size()-(lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]));
      if (nextmx[z]==-1)
      {
        cnt=1e9+10;
        break;
      }
      z=nextmx[z];
    }
    if (nextmx[z]==-1)
      continue;
    int f=lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),C)-begin(ans[ind[z]]);
    if (ans[ind[z]][f]<=D)
    {
      int g=lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]);
      cnt+=f-g;
      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 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Execution timed out 4026 ms 4752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 130 ms 5860 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 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 130 ms 5860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Execution timed out 4026 ms 4752 KB Time limit exceeded
4 Halted 0 ms 0 KB -