oj.uz

Submission #981367

# Submission time Handle Problem Language Result Execution time Memory
981367 2024-05-13T06:06:40 Z Muhammad_Aneeq Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 4000 ms 12080 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]={},premx[N]={};
bool vis[N]={};
vector<vector<int>>ans;
int ind[N]={};
bool uni=0;
void init(int N,vector<int> H) 
{
  uni=is_sorted(begin(H),end(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);
  }
  d={};
  for (int i=N-1;i>=0;i--)
  {
    premx[i]=-1;
    if (d.empty())
    {
      d.push_front(i);
      continue;
    }
    while (d.size()&&H[d.front()]<H[i])
    {
      premx[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);
        ind[z]=ans.size()-1;
      } 
    }
  }
}
int minimum_jumps(int A, int B, int C, int D) 
{
  if (uni)
    return C-B;

  int minsteps=1e9+10;
  for (int i=A;i<=B;i++)
  {
    int ex=0;
    int z=i;
    while (z!=-1)
    {
      if (ex>minsteps)
        break;
      int cnt=ex++;
      int prez=z;
      while (ans[ind[z]].back()<C&&z!=-1)
      {
        cnt+=ans[ind[z]].size()-(lower_bound(begin(ans[ind[z]]),end(ans[ind[z]]),z)-begin(ans[ind[z]]));
        if (nextmx[ans[ind[z]].back()]==-1)
        {
          cnt=1e9+10;
          break;
        }
        z=nextmx[ans[ind[z]].back()];
      }
      if (z==-1||cnt==1e9+10)
      {
        z=premx[prez];
        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);
      }
      z=premx[prez];
    }
  }
  if (minsteps==1e9+10)
    return -1;  
  return minsteps;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 61 ms 7572 KB Output is correct
4 Correct 545 ms 8024 KB Output is correct
5 Correct 504 ms 4300 KB Output is correct
6 Correct 574 ms 8268 KB Output is correct
7 Correct 418 ms 7516 KB Output is correct
8 Correct 566 ms 8264 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 2392 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Incorrect 3 ms 2392 KB Output isn't correct
9 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 2 ms 2592 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 51 ms 12080 KB Output is correct
6 Correct 106 ms 12076 KB Output is correct
7 Correct 15 ms 6156 KB Output is correct
8 Correct 102 ms 11732 KB Output is correct
9 Correct 15 ms 3688 KB Output is correct
10 Correct 56 ms 11716 KB Output is correct
11 Correct 21 ms 8256 KB Output is correct
12 Correct 45 ms 7980 KB Output is correct
13 Correct 37 ms 7984 KB Output is correct
14 Correct 86 ms 11532 KB Output is correct
15 Execution timed out 4054 ms 11632 KB Time limit exceeded
16 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 2 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 177 ms 5856 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 2 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 177 ms 5856 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 2388 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 61 ms 7572 KB Output is correct
4 Correct 545 ms 8024 KB Output is correct
5 Correct 504 ms 4300 KB Output is correct
6 Correct 574 ms 8268 KB Output is correct
7 Correct 418 ms 7516 KB Output is correct
8 Correct 566 ms 8264 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 2 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Incorrect 3 ms 2392 KB Output isn't correct
17 Halted 0 ms 0 KB -