#include "jumps.h"
#include<bits/stdc++.h>
#define sz size()
#define ll int
using namespace std;
const ll INF = 1e9;
const ll NN = 200200;
ll up[NN][20], dw[NN][20];
int n, ok = 1;
vector<vector<ll>> v;
vector<ll> h;
void init(int N, vector<int> H)
{
n = N;
h = H;
v.resize(n);
vector<ll> q;
for(ll i = 0; i < n; ++i)
up[i][0] = -1,
dw[i][0] = -1;
for(ll i = 0; i < n; ++i)
{
ok &= h[i] == i + 1;
while(q.sz && h[q.back()] < h[i])
v[q.back()].push_back(i),
up[q.back()][0] = i,
q.pop_back();
q.push_back(i);
}
q.clear();
for(ll i = n - 1; i >= 0; --i)
{
while(q.sz && h[q.back()] < h[i])
v[q.back()].push_back(i),
dw[q.back()][0] = i,
q.pop_back();
q.push_back(i);
}
for(ll i = 0; i < n; ++i)
if(dw[i][0] > up[i][0])
swap(up[i][0], dw[i][0]);
for(ll i = 0; i < n; ++i)
if(dw[i][0] < 0)
swap(up[i][0], dw[i][0]);
for(ll j = 1; j < 20; ++j)
for(ll i = 0; i < n; ++i)
{
up[i][j] = up[up[i][j - 1]][j - 1];
dw[i][j] = dw[dw[i][j - 1]][j - 1];
}
}
int minimum_jumps(int a, int b, int c, int d)
{
if(ok) return c - b;
if(a == b && c == d)
{
ll ans = 0;
for(ll j = 19; j >= 0; --j)
{
if(up[a][j] < 0) continue;
if(h[up[a][j]] <= h[d])
a = up[a][j], ans += (1 << j);
}
for(ll j = 19; j >= 0; --j)
{
if(dw[a][j] < 0) continue;
if(h[dw[a][j]] <= h[d])
a = dw[a][j], ans += (1 << j);
}
return a == d ? ans : -1;
}
vector<ll> dist(n, INF);
queue<ll> q;
for(ll i = a; i <= b; ++i)
{
dist[i] = 0;
q.push(i);
}
while(q.sz)
{
ll s = q.front();
q.pop();
for(ll t : v[s])
{
if(dist[t] < INF) continue;
dist[t] = dist[s] + 1;
q.push(t);
}
}
ll ans = INF;
for(ll i = c; i <= d; ++i)
ans = min(ans, dist[i]);
return ans < INF ? ans : -1;
}
//signed main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
3 |
Runtime error |
64 ms |
77836 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
3 |
Correct |
0 ms |
2392 KB |
Output is correct |
4 |
Runtime error |
43 ms |
50468 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
3 |
Correct |
0 ms |
2392 KB |
Output is correct |
4 |
Runtime error |
43 ms |
50468 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2392 KB |
Output is correct |
3 |
Runtime error |
64 ms |
77836 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |