Submission #1223662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223662		sokratisi	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	128 ms	70972 KiB

jumps

#include "jumps.h"
#include <vector>
#include <stack>
#include <cstdio>
#include <queue>
#include <math.h>

using namespace std;

int n, in;
vector<int> h;
vector<bool> vis;
vector<vector<int>> adj;
int sparse1[200005][20], sparse2[200005][20]; // maybe more
int sparsermqval[200005][20], sparsermqpos[200005][20];

void create_graph() {
    stack<int> s;
    for (int i = 0; i < n; i++) {
        // if (h[i] == 1) in = i;
        while (s.size() > 0 && h[i] > h[s.top()]) {
            adj[s.top()].push_back(i);
            s.pop();
        }
        s.push(i);
    }
    while (s.size() > 0) s.pop();
    for (int i = n-1; i >= 0; i--) {
        while (s.size() > 0 && h[i] > h[s.top()]) {
            adj[s.top()].push_back(i);
            s.pop();
        }
        s.push(i);
    }
}

// void print_graph() {
//     for (int i = 0; i < n; i++) {
//         printf("%d: ", i);
//         for (auto u: adj[i]) printf("%d ", u);
//         printf("\n");
//     }
// }

// void bfs() {
//     for (int i = 0; i < n+2; i++) dist[i] = 1e9;
//     for (int i = 0; i < n+2; i++) vis[i] = false;
//     queue<int> q;
//     q.push(n);
//     dist[n] = 0;
//     while (!q.empty()) {
//         int cur = q.front();
//         q.pop();
//         if (vis[cur]) continue;
//         vis[cur] = true;
//         for (auto u: adj[cur]) {
//             q.push(u);
//             dist[u] = min(dist[u], dist[cur]+1);
//         }
//     }
// }

// void print_dist() {
//     for (int i = 0; i < n+2; i++) {
//         printf("%d -> %d\n", i, dist[i]);
//     }
// }

void calc_sparse1(int s) {
    vis[s] = true;
    for (auto u: adj[s]) {
        if (!vis[u]) calc_sparse1(u);
    }
    sparse1[s][0] = s;
    for (auto u: adj[s]) {
        if (h[u] > h[sparse1[s][0]]) sparse1[s][0] = u;
    }
    for (int i = 1; i < 20; i++) sparse1[s][i] = sparse1[sparse1[s][i-1]][i-1];
}

void calc_sparse2(int s) {
    vis[s] = true;
    for (auto u: adj[s]) {
        if (!vis[u]) calc_sparse2(u);
    }
    if (adj[s].size() == 0) sparse2[s][0] = s;
    else {
        sparse2[s][0] = adj[s][0];
        for (auto u: adj[s]) {
            if (h[u] < h[sparse2[s][0]]) sparse2[s][0] = u;
        }
    }
    for (int i = 1; i < 20; i++) sparse2[s][i] = sparse2[sparse2[s][i-1]][i-1];
}

// void print_sparse() {
//     printf("SPARSE2:\n");
//     for (int i = 0; i < n; i++) {
//         printf("%d: ", i);
//         for (int j = 0; j < 4; j++) printf("%d ", sparse2[i][j]);
//         printf("\n");
//     }
//     printf("\n\n");
// }





void calc_sparsermq() {
    for (int i = 0; i < n; i++) {
        sparsermqpos[i][0] = i;
        sparsermqval[i][0] = h[i];
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            if (i + (1 << j) >= n) {
                sparsermqval[i][j] = sparsermqval[i][j-1];
                sparsermqpos[i][j] = sparsermqpos[i][j-1];
                continue;
            }
            int pos = min(i + (1 << (j-1)), n - (1 << (j-1)));
            if (sparsermqval[pos][j-1] > sparsermqval[i][j-1]) {
                sparsermqval[i][j] = sparsermqval[pos][j-1];
                sparsermqpos[i][j] = sparsermqpos[pos][j-1];    
            }
            else {
                sparsermqval[i][j] = sparsermqval[i][j-1];
                sparsermqpos[i][j] = sparsermqpos[i][j-1];    
            }
        }
    }
}


int rmq_pos(int a, int b) {
    int totalnums = b - a + 1;
    int sz = floor(log2(totalnums));
    if (sparsermqval[a][sz] < sparsermqval[b-(1<<sz)+1][sz]) {
        return sparsermqpos[a][sz];
    }
    return sparsermqpos[b-(1<<sz)+1][sz];
}

void print_sparsermq() {
    for (int i = 0; i < n; i++) {
        printf("%d: ", i);
        for (int j = 0; j < 4; j++) {
            printf("{%d, %d},  ", sparsermqval[i][j], sparsermqpos[i][j]);
        }
        printf("\n");
    }
}


void init(int Num, vector<int> Height) {
    n = Num;
    h = Height;
    adj.resize(n); // place n is fake out and place n+1 is fake in
    // dist.resize(n+2);
    vis.resize(n);
    create_graph();
    for (int i = 0; i < n; i++) if (!vis[i]) calc_sparse1(i);
    for (int i = 0; i < n; i++) vis[i] = false;
    for (int i = 0; i < n; i++) if (!vis[i]) calc_sparse2(i);
    // print_graph();
    // print_sparse();


    calc_sparsermq();
    // print_sparsermq();
}

int minimum_jumps(int a, int b, int c, int d) {
    int val = h[rmq_pos(b+1, c)];
    // i want my num to bew less than c
    int l = a, r = b;
    int dst = b + 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (h[m] > val) l = m+1;
        else {
            dst = m;
            r = m-1;
        }
    } 
    if (dst == b + 1) return -1;
    a = dst;



    int ans = 0;
    for (int i = 19; i >= 0; i--) {
        if (h[sparse1[a][i]] < h[c]) {
            a = sparse1[a][i];
            ans += 1<<i;
        }
    }

    if (sparse1[a][0] == c) return ans+1;
    // if all are greater you are fucked
    // just choose the smallest of the two
    for (int i = 19; i >= 0; i--) {
        if (h[sparse2[a][i]] < h[c]) {
            a = sparse2[a][i];
            ans += 1<<i;
        }
    }
    bool okay = false;
    for (auto u: adj[a]) if (h[u] <= h[c]) okay = true;
    if (okay) return ans + 1;
    return -1;
}

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