Submission #413043

#	Time	Username	Problem	Language	Result	Execution time	Memory
413043		veehz	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4046 ms	16796 KiB

jumps

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

const int INF = (int)1e9+71;

/* Segment Tree */
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
	/* S op(S a, S b) {} -> Value combine function */
	/* S e() {} -> Initial value */
	int _n;
	vector<S> d;
	segtree() : segtree(0) {}
	explicit segtree(int n) : segtree(vector<S>(n, e())) {}
	explicit segtree(const vector<S>& v) : _n(int(v.size())) {
		d.assign(4*_n, e());
		build(v);
	}
	void build(vector<S> a, int v=1, int tl=0, int tr=-1){
		if(tr == -1) tr = _n-1;
		if(tl == tr){
			d[v] = a[tl];
		} else {
			int tm = (tl + tr) / 2;
			build(a, v*2, tl, tm);
			build(a, v*2+1, tm+1, tr);
			d[v] = op(d[v*2], d[v*2+1]);
		}
	}
	int get_first(int l, int r, int x, int v=1, int lv=0, int rv=-1) {
		if(rv==-1) rv=_n-1;
		// cout << l << " " << r << " " << x << " " << v << " " << lv << " " << rv << endl;
	    if(lv > r || rv < l) return -1;
	    if(l <= lv && rv <= r) {
	        if(d[v] <= x) return -1;
	        while(lv != rv) {
	            int mid = lv + (rv-lv)/2;
	            if(d[2*v] > x) {
	                v = 2*v;
	                rv = mid;
	            } else {
	                v = 2*v+1;
	                lv = mid+1;
	            }
	        }
	        return lv;
	    }
	
	    int mid = lv + (rv-lv)/2;
	    int rs = get_first(l, r, x, 2*v, lv, mid);
	    if(rs != -1) return rs;
	    return get_first(l ,r, x, 2*v+1, mid+1, rv);
	}
	
	int get_last(int l, int r, int x, int v=1, int lv=0, int rv=-1) {
		
		if(rv==-1) rv=_n-1;
	    if(lv > r || rv < l) return -1;
	    if(l <= lv && rv <= r) {
	        if(d[v] <= x) return -1;
	        while(lv != rv) {
	            int mid = lv + (rv-lv)/2;
	            if(d[2*v+1] > x) {
	                v = 2*v+1;
	                lv = mid+1;
	            } else {
	                v = 2*v;
	                rv = mid;
	            }
	        }
	        return lv;
	    }
	
	    int mid = lv + (rv-lv)/2;
	    int rs = get_last(l ,r, x, 2*v+1, mid+1, rv);
	    if(rs != -1) return rs;
	    return get_last(l, r, x, 2*v, lv, mid);
	}
};
/* End: Segment Tree */

vector<int> Trees;
vector<vector<ll>> edges;
int n;

int op(int a, int b){ return max(a,b); }
int e() { return INF; }

void init(int N, vector<int> H) {
	n = N; Trees = H;
	segtree<int, op, e> st(H);
	edges.assign(n, {});
	for(int i=0;i<n;i++){
		if(i != 0){
			// find to the left
			int res = st.get_last(0, i-1, H[i]);
			if(res != -1) edges[i].pb(res);
		}
		if(i != n-1){
			// cout << i << " " << __LINE__ << endl;
			int res = st.get_first(i+1, n-1, H[i]);
			if(res != -1) edges[i].pb(res);
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	assert(A==B && C==D);
	vector<ll> distance;
	vector<bool> processed(n);
	distance.assign(n, INF);
	distance[A] = 0;
	priority_queue<ii> q;
	q.push({0,A});
	while (!q.empty()) {
		int a = q.top().second; q.pop();
		if (processed[a]) continue;
		processed[a] = true;
		for (auto b : edges[a]) {
			if (distance[a]+1 < distance[b]) {
				distance[b] = distance[a]+1;
				q.push({-distance[b],b});
			}
		}
	}
	return (distance[C]==INF?-1:distance[C]);
}

• 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