oj.uz

답안 #981276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981276 2024-05-13T03:42:25 Z Jawad_Akbar_JJ 밀림 점프 (APIO21_jumps) C++17
0 / 100
 4000 ms 20088 KB 
#include "jumps.h"
#include <iostream> 
#include <vector>
#include <queue>

using namespace std;
const int N = 2e5 + 10;
vector<int> nei[N];
int lft[N];
int rgt[N];
int Mn[N];
int seen[N];    

void init(int n,vector<int> h){
    vector<int> v;
    
    for (int i=0;i<n;i++)
        lft[i] = rgt[i] = -1;
    
    for (int i=0;i<n;i++){
        while (v.size() > 0 and h[v.back()] < h[i])
            rgt[v.back()] = i,v.pop_back();
        v.push_back(i);
    }
    v.clear();

    for (int i=n-1;i>=0;i--){
        while (v.size() > 0 and h[v.back()] < h[i])
            lft[v.back()] = i,v.pop_back();
        v.push_back(i);
    }

    for (int i=0;i<n;i++){
        if (lft[i] != -1)
            nei[i + 1].push_back(lft[i] + 1);
        if (rgt[i] != -1)
            nei[i + 1].push_back(rgt[i] + 1);
    }
}
int cur = 0;
int minimum_jumps(int A, int B, int C, int D) {
    cur++;
    queue<int> Q;

    for (int i=A+1;i<=B + 1;i++)
        Q.push(i),seen[i] = cur,Mn[i] = 0;

    while (!Q.empty()){
        int u = Q.front();
        if (u >= C+1 and u <= D+1)
            return Mn[u];
        Q.pop();
        for (int i : nei[u])
            if (seen[i] != cur)
                Mn[i] = Mn[u] + 1,Q.push(i);
    }
    return -1;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 2 ms 8024 KB Output is correct
4 Correct 2 ms 8024 KB Output is correct
5 Correct 29 ms 14336 KB Output is correct
6 Correct 39 ms 15780 KB Output is correct
7 Correct 19 ms 12076 KB Output is correct
8 Incorrect 38 ms 16044 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

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