Submission #518936

#	Time	Username	Problem	Language	Result	Execution time	Memory
518936		maomao90	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1196 ms	78348 KiB

jumps

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

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
#define MP make_pair
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define MAXN 200005
#define MAXL 20

int n;
vi h;
int lft[MAXL][MAXN], rht[MAXL][MAXN], big[MAXL][MAXN];
ii sp[MAXL][MAXN];

inline ii qsp(int s, int e) {
    int k = 31 - __builtin_clz(e - s + 1);
    return max(sp[k][s], sp[k][e - (1 << k) + 1]);
}

void init(int _n, vi _h) {
	n = _n;
	h = _h;
    {
        stack<int> stk;
        REP (i, 0, n) {
            while (!stk.empty() && h[stk.top()] < h[i]) {
                stk.pop();
            }
            if (!stk.empty()) {
                lft[0][i] = stk.top();
            } else {
                lft[0][i] = -1;
            }
            stk.push(i);
        }
    }
    {
        stack<int> stk;
        RREP (i, n - 1, 0) {
            while (!stk.empty() && h[stk.top()] < h[i]) {
                stk.pop();
            }
            if (!stk.empty()) {
                rht[0][i] = stk.top();
            } else {
                rht[0][i] = -1;
            }
            stk.push(i);
        }
    }
    REP (i, 0, n) {
        if (lft[0][i] == -1 || rht[0][i] == -1) {
            big[0][i] = -1;
        }
        if (h[lft[0][i]] > h[rht[0][i]]) {
            big[0][i] = lft[0][i];
        } else {
            big[0][i] = rht[0][i];
        }
    }
    REP (k, 1, MAXL) {
        REP (i, 0, n) {
            if (lft[k - 1][i] == -1) {
                lft[k][i] = -1;
            } else {
                lft[k][i] = lft[k - 1][lft[k - 1][i]];
            }
            if (rht[k - 1][i] == -1) {
                rht[k][i] = -1;
            } else {
                rht[k][i] = rht[k - 1][rht[k - 1][i]];
            }
            if (big[k - 1][i] == -1) {
                big[k][i] = -1;
            } else {
                big[k][i] = big[k - 1][big[k - 1][i]];
            }
        }
    }
    REP (i, 0, n) {
        sp[0][i] = MP(h[i], i);
    }
    REP (k, 1, MAXL) {
        REP (i, 0, n - (1 << k - 1)) {
            sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
        }
    }
}


int minimum_jumps(int a, int b, int c, int d) {
    if (b + 1 == c) {
        if (rht[0][b] == -1 || rht[0][b] > d) {
            return -1;
        } else {
            return 1;
        }
    }
    int rmx = qsp(c, d).FI, mmx = qsp(b + 1, c - 1).FI;
    if (mmx > rmx) {
        return -1;
    }
    int u = b;
    if (h[u] >= rmx) {
        return -1;
    }
    RREP (k, MAXL - 1, 0) {
        if (lft[k][u] == -1) continue;
        if (lft[k][u] >= a && h[lft[k][u]] < rmx) {
            u = lft[k][u];
        }
    }
    assert(h[u] < rmx);
    if (h[u] > mmx) {
        assert(rht[0][u] >= c && rht[0][u] <= d);
        return 1;
    }
    int ans = 0;
    RREP (k, MAXL - 1, 0) {
        if (big[k][u] == -1) continue;
        if (h[big[k][u]] < mmx) {
            u = big[k][u];
            ans += 1 << k;
        }
    }
    if (big[0][u] != -1 && h[big[0][u]] <= rmx) {
        assert(h[big[0][u]] >= mmx);
        assert(rht[0][big[0][u]] >= c && rht[0][big[0][u]] <= d);
        return ans + 2;
    }
    RREP (k, MAXL - 1, 0) {
        if (rht[k][u] == -1) continue;
        if (rht[k][u] < c) {
            u = rht[k][u];
            ans += 1 << k;
        }
    }
    if (rht[0][u] <= d) {
        assert(rht[0][u] >= c);
        return ans + 1;
    } else {
        return -1;
    }
}


/*
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
*/

Compilation message (stderr)

jumps.cpp: In function 'void init(int, vi)':
jumps.cpp:107:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  107 |         REP (i, 0, n - (1 << k - 1)) {
      |                              ~~^~~
jumps.cpp:5:42: note: in definition of macro 'REP'
    5 | #define REP(i, j, k) for (int i = j; i < k; i++)
      |                                          ^
jumps.cpp:108:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  108 |             sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 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