Submission #691518

#	Time	Username	Problem	Language	Result	Execution time	Memory
691518		Dan4Life	Rainforest Jumps (APIO21_jumps)	C++17	81 / 100	4090 ms	72308 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back

const int maxn = (int)2e5+10;
const int maxlg = 24;
const int INF = (int)1e9;

bool increasing;
vector<int> adj[maxn];
int n, h[maxn], dis[maxn], pr[maxn], nx[maxn];
int high[maxlg][maxn], low[maxlg][maxn], gis[maxlg][maxn];

int bfs(int s1, int s2, int d1, int d2){
    queue<int> Q;
    while(!Q.empty()) Q.pop();
    for(int i = 0; i < n; i++) dis[i]=INF;
    for(int i = s1; i <= s2; i++) Q.push(i), dis[i]=0;
    while(!Q.empty()){
        int s = Q.front(); Q.pop();
        if(d1<=s and s<=d2) return dis[s];
        for(auto u : adj[s])
            if(dis[u]==INF)
                dis[u] = dis[s]+1, Q.push(u);
    }
    return -1;
}

void calc(int jmp[][maxn]){
    for(int i = 1; i < maxlg; i++)
        for(int j = 0; j < n; j++)
            if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}

void init(int N, vector<int> a) {
    n = N; increasing = 1;
    stack<pair<int,int>> S;
    memset(pr,-1,sizeof(pr));
    memset(nx,-1,sizeof(nx));
    memset(gis,-1,sizeof(gis));
    memset(low,-1,sizeof(low));
    memset(high,-1,sizeof(high));
    for(int i = 0; i < (int)a.size(); i++) h[i]=a[i];
    for(int i = 0; i < n; i++){
        increasing&=(!i or a[i]>=a[i-1]);
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) pr[i] = S.top().se;
        S.push({a[i],i});
    }
    while(!S.empty()) S.pop();
    for(int i = n-1; i>=0; i--){
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) nx[i] = S.top().se;
        S.push({a[i],i});
    }
    while(!S.empty()) S.pop();
    for(int i = 0; i < n; i++){
        if(pr[i]!=-1) adj[i].pb(pr[i]), gis[0][i]=pr[i];
        if(nx[i]!=-1) adj[i].pb(nx[i]);
        if(pr[i]!=-1 and nx[i]!=-1){
            if(a[pr[i]]<a[nx[i]]) swap(pr[i],nx[i]);
            high[0][i] = pr[i]; low[0][i] = nx[i];
            if(a[pr[i]]>a[nx[i]]) swap(pr[i],nx[i]);
        }
        else{
            if(pr[i]!=-1) low[0][i] = pr[i];
            else low[0][i] = nx[i];
        }
    }
    calc(high), calc(low), calc(gis);
}

int get_path(int *x, int y, int jmp[][maxn]){
    int tot = 0;
    for(int i = 20; i >= 0; i--)
        if(jmp[i][*x]!=-1 and h[jmp[i][*x]]<=h[y])
            *x = jmp[i][*x], tot+=(1<<i);
    return tot;
}

int sub5(int x, int y){
    int num1 = get_path(&x,y,high);
    int num2 = get_path(&x,y,low);
    return (h[x]==h[y]?num1+num2:-1);
}

int getBest(int x, int y, int z){
    if(x==y) return x;
    for(int i = 20; i >= 0; i--)
        if(gis[i][y]>=x and h[gis[i][y]]<h[z])
            y = gis[i][y];
    return y;
}

int minimum_jumps(int A, int B, int C, int D) {
    if(increasing) return C-B;
    if(C==D) return sub5(getBest(A,B,C),C);
    return bfs(A,B,C,D);
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 0 / 19