oj.uz

답안 #413616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413616 2021-05-29T05:41:04 Z daniel920712 밀림 점프 (APIO21_jumps) C++14
0 / 100
 4000 ms 29076 KB 
#include "jumps.h"

#include <vector>
#include <queue>
#include <stack>
#include <stdio.h>
using namespace std;
int r[25][200005];
int l[25][200005];
int Pow[25];
stack < int > all;
vector < int > high;

void init(int N, std::vector<int> H)
{
    high=H;
    int i,j,k;
    Pow[0]=1;
    for(i=1;i<=20;i++) Pow[i]=Pow[i-1]*2;
    for(i=0;i<=20;i++)
    {
        for(j=0;j<N;j++)
        {
            r[i][j]=j;
            l[i][j]=j;
        }
    }
    for(i=0;i<N;i++)
    {
        while(!all.empty()&&H[all.top()]<H[i])
        {
            r[0][all.top()]=i;
            all.pop();
        }
        all.push(i);

    }
    while(!all.empty()) all.pop();
    for(i=N-1;i>=0;i--)
    {
        while(!all.empty()&&H[all.top()]<H[i])
        {
            l[0][all.top()]=i;
            all.pop();
        }
        all.push(i);
    }
    while(!all.empty()) all.pop();
    for(i=1;i<=20;i++)
    {
        for(j=0;j<N;j++)
        {
            for(k=l[i-1][j];k<=r[i-1][j];k++)
            {
                l[i][j]=min(l[i][j],l[i-1][k]);
                r[i][j]=max(r[i][j],r[i-1][k]);
            }
        }
    }
    return ;
}

int minimum_jumps(int A, int B, int C, int D)
{
    int ans=0,now=A,i,j,ll=A,rr=B,x,y,ok=0;
    for(i=A;i<=B;i++) for(j=C;j<=D;j++) ok=ok||(high[j]>high[i]);
    if(!ok) return -1;
    if(!(B<C||D<A)) return 0;
    for(i=20;i>=0;i--)
    {
        x=ll;
        y=rr;
        for(j=ll;j<=rr;j++)
        {
            x=min(x,l[i][j]);
            y=max(y,r[i][j]);
        }
        //printf("%d %d %d %d %d\n",ll,rr,x,y,i);
        if(y<C||D<x)
        {
            ans+=Pow[i];
            ll=x;
            rr=y;
        }

    }
    x=ll;
    y=rr;
    for(j=ll;j<=rr;j++)
    {
        x=min(x,l[0][j]);
        y=max(y,r[0][j]);
    }
    //printf("%d %d %d %d\n",ll,rr,x,y);
    if(y<C||D<x)
    {
        return -1;
    }

    return ans+1;
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:65:15: warning: unused variable 'now' [-Wunused-variable]
   65 |     int ans=0,now=A,i,j,ll=A,rr=B,x,y,ok=0;
      |               ^~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Execution timed out 4041 ms 29076 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Incorrect 2 ms 456 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Incorrect 2 ms 456 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Execution timed out 4046 ms 28684 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Execution timed out 4070 ms 16516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Execution timed out 4070 ms 16516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Execution timed out 4041 ms 29076 KB Time limit exceeded
4 Halted 0 ms 0 KB -