Submission #1031895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031895		mispertion	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	921 ms	49788 KiB

jumps

#include <bits/stdc++.h>
                         
        using namespace std;
 
        int N;
        vector<int> H;
        int L[200005][20], R[200005][20], UP[200005][20];
 
        void init(int _N, vector<int> _H) {
            N = _N, swap(H, _H);
            H.push_back(0);
            for(int l = 0; l <= N; l++) 
                L[l][0] = R[l][0] = UP[l][0] = N;
 
            stack<int> ST;
            for(int l = 0; l < N; l++) {
                while(!ST.empty() && H[ST.top()] < H[l]) ST.pop();
                if(!ST.empty()) L[l][0] = ST.top();
                ST.push(l);
            }
 
            while(!ST.empty()) ST.pop();
 
            for(int l = N - 1; l >= 0; l--) {
                while(!ST.empty() && H[ST.top()] < H[l]) ST.pop();
                if(!ST.empty()) R[l][0] = ST.top();
                ST.push(l);
            }
 
            for(int l = 0; l < N; l++) 
                UP[l][0] = (H[L[l][0]] > H[R[l][0]] ? L[l][0] : R[l][0]);
            
            for(int l = 1; l < 20; l++)
                for(int i = 0; i <= N; i++)
                    L[i][l] = L[L[i][l - 1]][l - 1],
                    R[i][l] = R[R[i][l - 1]][l - 1],
                    UP[i][l] = UP[UP[i][l - 1]][l - 1];
        }
 
        int minimum_jumps(int A, int B, int C, int D) {
            int ans = B;
            for(int l = 19; l >= 0; l--)
                if(L[ans][l] >= A && R[L[ans][l]][0] <= D) ans = L[ans][l];
            if(R[ans][0] >= C && R[ans][0] <= D) return 1;
 
            int res = 0;
            for(int l = 19; l >= 0; l--)
                if(R[UP[ans][l]][0] < C) 
                    ans = UP[ans][l], res += (1 << l);
 
            if(R[UP[ans][0]][0] >= C && R[UP[ans][0]][0] <= D) return res + 2;
 
            for(int l = 19; l >= 0; l--)
                if(R[ans][l] < C) ans = R[ans][l], res += (1 << l);
            
            if(R[ans][0] >= C && R[ans][0] <= D) return res + 1;
            return -1;
        }

• 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