이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define all(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }
template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }
const ll NN = 2e5 + 10;
const ll INF = 1e9 + 1;
ll n;
vl graph[NN];
const ll L = 20;
ll lift[NN][L];
ll liftSmall[NN][L];
ll h[NN];
void init(int _N, std::vector<int> H) {
n = _N;
copy(all(H), h);
vl lst(n);
F(i, 0, n) {
lst[i] = i - 1;
while (lst[i] != -1 and H[lst[i]] < H[i]) lst[i] = lst[lst[i]];
if (lst[i] != -1) graph[i].push_back(lst[i]);
}
FD(i, n-1, -1) {
lst[i] = i + 1;
while (lst[i] != n and H[lst[i]] < H[i]) lst[i] = lst[lst[i]];
if (lst[i] != n) graph[i].push_back(lst[i]);
}
vl idx(n); iota(all(idx), 0ll);
sort(all(idx), [&](ll a, ll b) {
return H[a] > H[b];
});
F(j, 0, L) lift[n][j] = liftSmall[n][j] = n;
for (auto i: idx) {
lift[i][0] = liftSmall[i][0] = n;
sort(all(graph[i]), [&](ll a, ll b) {
return H[a] > H[b];
});
if (graph[i].size() >= 1) {
lift[i][0] = graph[i][0];
}
if (graph[i].size() == 2) liftSmall[i][0] = graph[i][1];
F(j, 1, L) {
lift[i][j] = lift[lift[i][j-1]][j-1];
liftSmall[i][j] = liftSmall[liftSmall[i][j-1]][j-1];
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if (A == B and C == D) {
ll cost = 0;
FD(l, L-1, -1) {
if (lift[A][l] != n and h[lift[A][l]] <= h[C]) {
A = lift[A][l];
cost += 1 << l;
}
}
FD(l, L-1, -1) {
if (liftSmall[A][l] != n and h[liftSmall[A][l]] <= h[C]) {
A = liftSmall[A][l];
cost += 1 << l;
}
}
if (A != C) return -1;
return cost;
} else return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |