Submission #518350

#	Time	Username	Problem	Language	Result	Execution time	Memory
518350		maomao90	Rainforest Jumps (APIO21_jumps)	C++17	27 / 100	1433 ms	179128 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 p[2][MAXL][MAXN];
ii sp[2][MAXL][MAXN];

inline ii qsp(bool b, int s, int e) {
    int k = 31 - __builtin_clz(e - s + 1);
    return max(sp[b][k][s], sp[b][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()) {
                p[0][0][i] = stk.top();
            } else {
                p[0][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()) {
                p[1][0][i] = stk.top();
            } else {
                p[1][0][i] = -1;
            }
            stk.push(i);
        }
    }
    REP (i, 0, n) {
        if (p[0][0][i] == -1) {
            swap(p[0][0][i], p[1][0][i]);
        }
        if (p[1][0][i] != -1) {
            if (h[p[0][0][i]] < h[p[1][0][i]]) {
                swap(p[0][0][i], p[1][0][i]);
            }
        }
        debug("%d: %d %d\n", i, p[0][0][i], p[1][0][i]);
    }
    debug("\n");
    REP (z, 0, 2) {
        REP (k, 1, MAXL) {
            REP (i, 0, n) {
                if (p[z][k - 1][i] == -1) {
                    p[z][k][i] = -1;
                } else {
                    p[z][k][i] = p[z][k - 1][p[z][k - 1][i]];
                }
            }
        }
    }
    REP (i, 0, n) {
        sp[0][0][i] = sp[1][0][i] = MP(h[i], i);
    }
    REP (k, 1, MAXL) {
        REP (i, 0, n - (1 << k - 1)) {
            sp[0][k][i] = max(sp[0][k - 1][i], sp[0][k - 1][i + (1 << k - 1)]);
            sp[1][k][i] = min(sp[1][k - 1][i], sp[1][k - 1][i + (1 << k - 1)]);
        }
    }
}

ii jump(bool b, int u, int mx, int s = 0, int e = n - 1) {
    int pc = 0;
    RREP (k, MAXL - 1, 0) {
        if (p[b][k][u] < s || p[b][k][u] > e) continue;
        if (h[p[b][k][u]] <= mx) {
            u = p[b][k][u];
            pc += 1 << k;
        }
    }
    return MP(u, pc);
}

int minimum_jumps(int a, int b, int c, int d) {
    if (b + 1 == c) {
        if ((p[0][0][b] >= c && p[0][0][b] <= d) || 
                (p[1][0][b] >= c && p[1][0][b] <= d)) {
            return 1;
        } else {
            return -1;
        }
    }
    int rmx = qsp(0, c, d).FI, mmx = qsp(0, b + 1, c - 1).FI;
    int u, pc;
    u = qsp(1, a, b).SE;
    debug("%d %d %d\n", rmx, mmx, u);
    if (mmx > rmx || h[u] > rmx) {
        return -1;
    }
    int res = 0;
    tie(u, pc) = jump(0, u, rmx - 1, a, b);
    tie(u, pc) = jump(1, u, rmx - 1, a, b);
    debug(" %d\n", u);
    if (h[u] < mmx) {
        tie(u, pc) = jump(0, u, mmx - 1);
        debug(" %d %d\n", u, pc);
        res += pc;
        pc = 0;
        debug(" %d %d\n", p[0][0][u], h[p[0][0][u]]);
        if (p[0][0][u] != -1 && h[p[0][0][u]] <= rmx) {
            u = p[0][0][u];
            pc++;
        } else {
            RREP (k, MAXL - 1, 0) {
                if (p[1][k][u] == -1) continue;
                if (h[p[1][k][u]] <= mmx - 1) {
                    u = p[1][k][u];
                    pc += 1 << k;
                }
            }
            u = p[1][0][u];
            pc++;
        }
    }
    assert(h[u] >= mmx && h[u] <= rmx && u < c);
    res += pc + 1;
    return res;
}


/*
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:101:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  101 |         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:102:73: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  102 |             sp[0][k][i] = max(sp[0][k - 1][i], sp[0][k - 1][i + (1 << k - 1)]);
      |                                                                       ~~^~~
jumps.cpp:103:73: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  103 |             sp[1][k][i] = min(sp[1][k - 1][i], sp[1][k - 1][i + (1 << k - 1)]);
      |                                                                       ~~^~~

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