제출 #1282079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282079		duckindog	밀림 점프 (APIO21_jumps)	C++20	100 / 100	469 ms	47416 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200'000 + 10,
            MAX = 1'000'000,
            LG = 17;

int n;
int h[MAXN];

namespace ST { 
    int st[MAXN][LG + 1];
    void init() { 
        for (int i = 0; i < n; ++i) st[i][0] = i;
        for (int j = 1; j <= LG; ++j) { 
            for (int i = 0; i <= (n - 1) - (1 << j) + 1; ++i) { 
                int lt = st[i][j - 1], rt = st[i + (1 << (j - 1))][j - 1];
                st[i][j] = (h[lt] > h[rt] ? lt : rt);
            }
        }
    }

    int get(int l, int r) { 
        int j = __lg(r - l + 1);
        int lt = st[l][j], rt = st[r - (1 << j) + 1][j];
        return h[lt] > h[rt] ? lt : rt;
    }
}

int goL[MAXN], goR[MAXN];
int up[MAXN][LG + 1], upR[MAXN][LG + 1];
void init(int N, std::vector<int> H) {
    n = N;
    for (int i = 0; i < n; ++i) h[i] = H[i];
    { // go left
        stack<int> st;
        for (int i = 0; i < n; ++i) { 
            while (st.size() && h[st.top()] < h[i]) st.pop();
            goL[i] = (st.size() ? st.top() : n);
            st.push(i);
        }
    }
    { // go right
        stack<int> st;
        for (int i = n - 1; i >= 0; --i) { 
            while (st.size() && h[st.top()] < h[i]) st.pop();
            goR[i] = (st.size() ? st.top() : n);
            st.push(i);
        }
    }
    
    h[n] = -1;
    fill(up[n], up[n] + LG + 1, n);
    for (int i = 0; i < n; ++i) { 
        up[i][0] = (h[goR[i]] > h[goL[i]] ? goR[i] : goL[i]);
    }
    
    h[n] = MAX;
    fill(upR[n], upR[n] + LG + 1, n);
    for (int i = 0; i < n; ++i) { 
        upR[i][0] = (h[goR[i]] < h[goL[i]] ? goR[i] : goL[i]);
    }

    for (int j = 1; j <= LG; ++j) { 
        for (int i = 0; i < n; ++i) { 
            up[i][j] = up[up[i][j - 1]][j - 1];
            upR[i][j] = upR[upR[i][j - 1]][j - 1];
        }
    }
    
    ST::init();
}

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

    int X = ST::get(B, D);
    { // bin search
        int le = A, ri = B, it = B;
        while (le <= ri) { 
            int mid = (le + ri) >> 1;
            if (h[ST::get(mid, B)] <= h[X]) ri = mid - 1, it = mid;
            else le = mid + 1;
        }
        A = ST::get(it, B);
    }
    
    int Y = ST::get(B, C - 1);
    for (int j = LG; j >= 0; --j) { 
        if (h[up[A][j]] <= h[Y]) { 
            ret += (1 << j);
            A = up[A][j];
        }
    }

    int answer = MAX;
    if (h[up[A][0]] >= h[Y] && h[up[A][0]] <= h[X]) { 
        int _A = up[A][0];
        if (C <= _A && _A <= D) answer = min(answer, ret + 1);
        if (C <= goR[_A] && goR[_A] <= D) answer = min(answer, ret + 2);
    }

    for (int j = LG; j >= 0; --j) { 
        if (h[upR[A][j]] <= h[Y]) { 
            ret += (1 << j);
            A = upR[A][j];
        }
    }
    ret += 1;
    A = goR[A];
    if (C <= A && A <= D) answer = min(answer, ret);
    
    return answer == MAX ? -1 : answer;
}

• 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: 19 / 19