| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 947454 | starchan | Rainforest Jumps (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int LOGM = 19;
const int MX = 2e5+5;
vector<int> arr;
int l[LOGM][MX];
int r[LOGM][MX];
int up[LOGM][MX];
int min_jumps(int x, int y)
{
int ans = 0;
for(int i = LOGM-1; i >= 1; i--)
{
int v = up[i][x];
if(arr[v] <= arr[y])
{
ans+=(1ll<<i);
x = v;
}
}
for(int i = LOGM-1; i >= 1; i--)
{
int v = l[i][x];
if(arr[v] <= arr[y])
{
ans+=(1ll<<i);
x = v;
}
}
if(x == y)
return ans;
return -1;
}
int minimum_jumps(int a, int b, int c, int d)
{
a++; b++; c++; d++;
return min_jumps(a, c);
}
void init(int n, vector<int> h)
{
arr.resize(n+2);
for(int i = 1; i <= n; i++)
arr[i] = h[i-1];
arr[0] = INF;
arr[n+1] = INF;
l[0][0] = 0;
r[0][0] = n+1;
l[0][n+1] = 0;
r[0][n+1] = n+1;
for(int i = 1; i <= n; i++)
{
l[0][i] = i-1;
r[0][i] = i+1;
}
for(int i = 1; i <= n; i++)
{
while(arr[l[0][i]] <= arr[i])
l[0][i] = l[0][l[0][i]];
}
for(int i = n; i >= 1; i--)
{
while(arr[l[0][i]] <= arr[i])
r[0][i] = r[0][r[0][i]];
}
for(int i = 0; i <= n+1; i++)
{
if(arr[l[0][i]] >= arr[r[0][i]])
up[0][i] = l[0][i];
else
up[0][i] = r[0][i];
}
for(int i = 1; i < LOGM; i++)
{
for(int u = 0; u <= n+1; u++)
{
l[i][u] = l[i-1][l[i-1][u]];
r[i][u] = r[i-1][r[i-1][u]];
up[i][u] = up[i-1][up[i-1][u]];
}
}
}