#include <bits/stdc++.h>
#include "jumps.h"
//#include "stub.cpp"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
#define all(x) x.begin(),x.end()
#define pb push_back
vvi g;
int n=-1;
void init(int N, vi h){
n=N;
g.resize(n);
vi nxt(n,-1),prv(n,-1);
stack<int>s;
for(int i=0; i<n; i++){
while(s.size() && h[i]>h[s.top()]){
nxt[s.top()]=i;
s.pop();
}
s.push(i);
}
while(s.size())
s.pop();
for(int i=n-1; 0<=i ;i--){
while(s.size() && h[i]>h[s.top()]){
prv[s.top()]=i;
s.pop();
}
s.push(i);
}
for(int i=0; i<n;i ++){
if(nxt[i]!=-1)
g[i].pb(nxt[i]);
if(prv[i]!=-1)
g[i].pb(prv[i]);
}
}
int minimum_jumps(int A, int B, int C, int D){
return C-B;
vector<bool>vis(n);
queue<pi>q;
for(int i=A; i<=B; i++)
q.push({0,i});
while(q.size()){
pi cur=q.front();
q.pop();
int src=cur.second,dst=cur.first;
if(C<= src && src<=D)
return dst;
if(vis[src])continue;
vis[src]=1;
for(int nbr:g[src])
if(!vis[nbr])
q.push({dst+1,nbr});
}
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
151 ms |
12096 KB |
Output is correct |
4 |
Correct |
994 ms |
15136 KB |
Output is correct |
5 |
Correct |
1103 ms |
7744 KB |
Output is correct |
6 |
Correct |
826 ms |
15168 KB |
Output is correct |
7 |
Correct |
686 ms |
10388 KB |
Output is correct |
8 |
Correct |
985 ms |
15144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
151 ms |
12096 KB |
Output is correct |
4 |
Correct |
994 ms |
15136 KB |
Output is correct |
5 |
Correct |
1103 ms |
7744 KB |
Output is correct |
6 |
Correct |
826 ms |
15168 KB |
Output is correct |
7 |
Correct |
686 ms |
10388 KB |
Output is correct |
8 |
Correct |
985 ms |
15144 KB |
Output is correct |
9 |
Incorrect |
1 ms |
200 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |