Submission #1162887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162887		tw20000807	Rainforest Jumps (APIO21_jumps)	C++20	48 / 100	484 ms	51308 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;

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] = max(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    int query(int l, int r){
        int lg = __lg(r - l + 1);
        return max(dp[lg][l], dp[lg][r - (1 << lg) + 1]);
    }
};
TABLE RMQ;
vector< vector< int > > big, rig;
vector< int > h, p;
void init(int n, vector<int> H) {
	h = H;
	p.resize(n + 2);
    vector< int > l(n, n), r(n, n);
	h.push_back(n + 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() ? n : stk.back();
            stk.push_back(i);
        }
    }
    RMQ = TABLE(h);
    big.resize(20, vector< int >(n + 1));
	rig.resize(20, vector< int >(n + 1));
    for(int i = 0; i < n; ++i){
		p[h[i]] = i;
		if(h[l[i]] > h[r[i]]) big[0][i] = l[i];
		else big[0][i] = r[i];
		rig[0][i] = r[i];
    }
	big[0][n] = rig[0][n] = n;
	for(int i = 1; i < 20; ++i){
		for(int j = 0; j <= n; ++j){
			big[i][j] = big[i - 1][big[i - 1][j]];
			rig[i][j] = rig[i - 1][rig[i - 1][j]];
		}
	}
}

int minimum_jumps(int a, int b, int c, int d) {
	int l = a, r = b, ans = b;
	int hi = p[RMQ.query(c, d)];
	while(l <= r){
		int mid = (l + r) >> 1;
		int t = RMQ.query(mid, b);
		if(RMQ.query(mid, b) <= h[hi]){
			ans = p[t];
			r = mid - 1;
		}
		else l = mid + 1;
	}

    int now = ans;
	int cnt = 0;
	for(int i = 19; i >= 0; --i){
		int bjump = big[i][now], rjump = rig[i][now];
		if(c <= rjump) continue;
		if(bjump >= c) continue;
		if(h[bjump] > h[hi]) continue;
		now = bjump; cnt += (1 << i);
	}
	for(int i = 19; i >= 0; --i){
		int jump = rig[i][now];
		if(jump >= c) continue;

		now = rig[i][now];
		cnt += (1 << i);
	}
	now = rig[0][now];
	++cnt;
	if(c <= now && now <= d) return cnt;
	return -1;
}

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