Submission #1217490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217490		jasonic	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	1127 ms	43540 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

int n;
int h[200005];
int leftJump[200005];
int rightJump[200005];

int weakDepth[200005];
int strongDepth[200005];

int weakJump[200005][20];
int strongJump[200005][20];

void init(int N, vector<int> heights) {
    
    // hello little space complexity
    memset(leftJump, -1, sizeof(leftJump));
    memset(rightJump, -1, sizeof(rightJump));
    memset(weakJump, -1, sizeof(weakJump));
    memset(strongJump, -1, sizeof(strongJump));
    memset(weakDepth, -1, sizeof(weakDepth));
    memset(strongDepth, -1, sizeof(strongDepth));

    n = N;
    for(int i = 0; i < n; i++) h[i] = heights[i];
    
    // monotonic stack ftw
    stack<pair<int, int>> maxStack;
    maxStack.push(make_pair(n+1, -1));

    for(int i = 0; i < n; i++) {
        while(maxStack.top().first <= h[i]) maxStack.pop();
        if(maxStack.top().second > -1) leftJump[i] = maxStack.top().second;
        maxStack.push(make_pair(h[i], i));
    }

    while(!maxStack.empty()) maxStack.pop();

    maxStack.push(make_pair(n+1, n));

    for(int i = n-1; i >= 0; i--) {
        while(maxStack.top().first <= h[i]) maxStack.pop();
        if(maxStack.top().second < n) rightJump[i] = maxStack.top().second;
        maxStack.push(make_pair(h[i], i));
    }

    for(int i = 0; i < n; i++) {
        if(leftJump[i] == -1 && rightJump[i] == -1) continue;
        else if(leftJump[i] != -1 && rightJump[i] != -1) {
            if(h[leftJump[i]] < h[rightJump[i]]) {
                weakJump[i][0] = leftJump[i];
            } else {
                weakJump[i][0] = rightJump[i];
            }
        } else weakJump[i][0] = max(leftJump[i], rightJump[i]);
        
        if(h[leftJump[i]] < h[rightJump[i]]) {
            strongJump[i][0] = rightJump[i];
        } else strongJump[i][0] = leftJump[i];
    }

    // for(int i = 0; i < n; i++) {
    //     cout << i << ' ' << weakJump[i][0] << ' ' << strongJump[i][0] << '\n';
    // }

    auto dfsWeak = [&](auto &&dfsWeak, int v) -> void {

        if(weakDepth[v] != -1) return;

        if(weakJump[v][0] != -1) {
            dfsWeak(dfsWeak, weakJump[v][0]);
            weakDepth[v] = max(weakDepth[v], weakDepth[weakJump[v][0]] + 1);
        }

        weakDepth[v] = max(weakDepth[v], 0);

        for(int i = 1; 1ll<<i <= weakDepth[v]; i++) {
            weakJump[v][i] = weakJump[weakJump[v][i-1]][i-1];
            // printf("weak %d %d goes to %d\n", v, 1<<i, weakJump[v][i]);
        }
    };

    auto dfsStrong = [&](auto &&dfsStrong, int v) -> void {

        if(strongDepth[v] != -1) return;

        if(strongJump[v][0] != -1) {
            dfsStrong(dfsStrong, strongJump[v][0]);
            strongDepth[v] = max(strongDepth[v], strongDepth[strongJump[v][0]] + 1);
        }

        strongDepth[v] = max(strongDepth[v], 0);

        for(int i = 1; 1ll<<i <= strongDepth[v]; i++) {
            strongJump[v][i] = strongJump[strongJump[v][i-1]][i-1];
            // printf("strong %d %d goes to %d\n", v, 1<<i, strongJump[v][i]);
        }
    };

    for(int i = 0; i < n; i++) {
        if(weakJump[i][0] != -1) dfsWeak(dfsWeak, i);
        if(strongJump[i][0] != -1)dfsStrong(dfsStrong, i);
    }
}

int strongJumps(int v, int x) {
    int res = v;
    for(int i = 19; i >= 0; i--) {
        if(strongJump[res][i] != -1) if(x >= (1ll<<i)) {
            res = strongJump[res][i];
            x -= (1ll<<i);
        }
    }
    return res;
}

int minimum_jumps(int A, int B, int C, int D) {
    assert(A == B);
    assert(C == D);

    int l = -1, r = strongDepth[A]+1;
    int x = -1;
    while(l+1 < r) {
        int m = (l+r)/2;
        // cout << "checking " << m << '\n';
        int s = strongJumps(A, m);
        // cout << "from " << A << " to " << s << '\n';
        int js = 0;

        for(int i = 19; i >= 0; i--) {
            if(weakJump[s][i] != -1) {
                // cout << "try to jump by " << (1ll<<i) << '\n';
                if(h[weakJump[s][i]] <= h[C]) {
                    // cout << "jumped by " << (1ll<<i) << '\n';
                    s = weakJump[s][i];
                    js += 1ll<<i;
                    // cout << s << '\n';
                }
            }
        }

        if(s == C) {
            // cout << "# of jumps: " << js+m << '\n';
            x = js + m;
            l = m;
        }
        else r = m;
    }

    // printf("%d %d\n", l, r);

    return x;
}

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