제출 #1162872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162872		tw20000807	Rainforest Jumps (APIO21_jumps)	C++20	33 / 100	4016 ms	5552 KiB

jumps

#include<bits/stdc++.h>

#define ll long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const ll llmx = 1e9;
struct TABLE{
    int n;
    int g;
    vector< vector< int > > dp;
    TABLE(){}
    TABLE(vector< int > &v){
        n = SZ(v);
        g = __lg(n) + 1;
        dp.resize(g, vector< int >(n));
        for(int i = 0; i < n; ++i){
            dp[0][i] = v[i];
        }
        for(int j = 1; j < g; ++j){
            for(int i = 0; i + (1 << j) - 1 < n; ++i){
                dp[j][i] = min(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    int query(int l, int r){
        int lg = __lg(r - l + 1);
        return min(dp[lg][l], dp[lg][r - (1 << lg) + 1]);
    }
};
int n;
vector< TABLE > mn;
vector< vector< int > > dis;
vector< int > l, r;
void init(int N, vector<int> h) {
	n = N;
	l.resize(n + 1, -1); r.resize(n + 1, -1);
    {
        vector< int > stk;
        for(int i = 0; i < n; ++i){
            while(!stk.empty() && h[stk.back()] < h[i]){
                r[stk.back()] = i;
                stk.pop_back();
            }
            l[i] = stk.empty() ? -1 : stk.back();
            stk.push_back(i);
        }
    }
}

int minimum_jumps(int a, int b, int c, int d) {
    vector< int > dis(n + 1, llmx);
	vector< int > dq;
	for(int i = a; i <= b; ++i) dis[i] = 0, dq.push_back(i);
	int id = 0;
	while(id < SZ(dq)){
		int cur = dq[id++];
		for(auto nxt : {l[cur], r[cur]}) if(nxt != -1) {
			if(dis[nxt] > dis[cur] + 1){
				dis[nxt] = dis[cur] + 1;
				dq.push_back(nxt);
			}
		}
	}
	int ans = llmx;
	for(int i = c; i <= d; ++i) ans = min(ans, dis[i]);
	if(ans == llmx) return -1;
	return ans;
}

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