답안 #983841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983841	2024-05-16T07:14:07 Z	The_Samurai	밀림 점프 (APIO21_jumps)	C++17	0 / 100	4000 ms	4356 KB

jumps

#include "jumps.h"
#include "bits/stdc++.h"
using namespace std;

const int lg = 18, N = 2e5 + 5, inf = 1e9;
vector<int> l(N), r(N);
int n;

void init(int N, vector<int> H) {
    n = N;
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() and H[s.top()] < H[i]) s.pop();
        r[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = 0; i < n; i++) {
        while (!s.empty() and H[s.top()] < H[i]) s.pop();
        l[i] = s.empty() ? -1 : s.top();
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    queue<int> q;
    vector<int> ans(n, inf);
    for (int i = a; i <= b; i++) ans[i] = 0, q.push(i);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (c <= x and x <= d) return ans[x];
        if (l[x] >= 0 and ans[l[x]] > ans[x] + 1) {
            ans[l[x]] = ans[x] + 1;
            q.push(l[x]);
        }
        if (r[x] < n and ans[r[x]] > ans[x] + 1) {
            ans[r[x]] = ans[x] + 1;
            q.push(r[x]);
        }
    }
    return -1;
}

Subtask #1

0 / 4.0

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

Subtask #2

0 / 8.0

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

Subtask #3

0 / 13.0

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

Subtask #4

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1880 KB	Output is correct
2	Correct	1 ms	1876 KB	Output is correct
3	Correct	1 ms	1880 KB	Output is correct
4	Correct	1 ms	1880 KB	Output is correct
5	Correct	17 ms	3620 KB	Output is correct
6	Correct	23 ms	3800 KB	Output is correct
7	Correct	9 ms	2780 KB	Output is correct
8	Correct	27 ms	4344 KB	Output is correct
9	Correct	3 ms	2248 KB	Output is correct
10	Correct	21 ms	3804 KB	Output is correct
11	Correct	29 ms	4356 KB	Output is correct
12	Correct	19 ms	4072 KB	Output is correct
13	Incorrect	21 ms	4156 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

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

Subtask #6

0 / 21.0

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

Subtask #7

0 / 19.0

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