oj.uz

Submission #518350

# Submission time Handle Problem Language Result Execution time Memory
518350 2022-01-23T13:41:33 Z maomao90 Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1433 ms 179128 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 204 ms 70808 KB Output is correct
4 Correct 1312 ms 89448 KB Output is correct
5 Correct 1273 ms 44080 KB Output is correct
6 Correct 1433 ms 89452 KB Output is correct
7 Correct 1118 ms 60240 KB Output is correct
8 Correct 1288 ms 89480 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Runtime error 3 ms 912 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Runtime error 3 ms 912 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 69 ms 71440 KB Output is correct
6 Correct 83 ms 89316 KB Output is correct
7 Correct 46 ms 44648 KB Output is correct
8 Incorrect 87 ms 89372 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 196 ms 39696 KB Output is correct
5 Correct 829 ms 89348 KB Output is correct
6 Correct 618 ms 13888 KB Output is correct
7 Correct 967 ms 89360 KB Output is correct
8 Correct 683 ms 29600 KB Output is correct
9 Correct 889 ms 89372 KB Output is correct
10 Correct 1102 ms 89476 KB Output is correct
11 Correct 1044 ms 89648 KB Output is correct
12 Correct 1106 ms 89484 KB Output is correct
13 Correct 787 ms 89360 KB Output is correct
14 Correct 1307 ms 89740 KB Output is correct
15 Correct 962 ms 90128 KB Output is correct
16 Correct 748 ms 90264 KB Output is correct
17 Correct 1 ms 448 KB Output is correct
18 Correct 1 ms 456 KB Output is correct
19 Correct 2 ms 456 KB Output is correct
20 Correct 2 ms 668 KB Output is correct
21 Correct 2 ms 676 KB Output is correct
22 Correct 2 ms 656 KB Output is correct
23 Correct 4 ms 680 KB Output is correct
24 Correct 2 ms 676 KB Output is correct
25 Correct 1 ms 584 KB Output is correct
26 Correct 1 ms 840 KB Output is correct
27 Correct 22 ms 1224 KB Output is correct
28 Correct 19 ms 1352 KB Output is correct
29 Correct 23 ms 1352 KB Output is correct
30 Correct 16 ms 1352 KB Output is correct
31 Correct 20 ms 1352 KB Output is correct
32 Correct 0 ms 456 KB Output is correct
33 Correct 44 ms 50712 KB Output is correct
34 Correct 78 ms 89348 KB Output is correct
35 Correct 74 ms 89456 KB Output is correct
36 Correct 80 ms 89364 KB Output is correct
37 Correct 82 ms 89836 KB Output is correct
38 Correct 82 ms 90176 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 196 ms 39696 KB Output is correct
5 Correct 829 ms 89348 KB Output is correct
6 Correct 618 ms 13888 KB Output is correct
7 Correct 967 ms 89360 KB Output is correct
8 Correct 683 ms 29600 KB Output is correct
9 Correct 889 ms 89372 KB Output is correct
10 Correct 1102 ms 89476 KB Output is correct
11 Correct 1044 ms 89648 KB Output is correct
12 Correct 1106 ms 89484 KB Output is correct
13 Correct 787 ms 89360 KB Output is correct
14 Correct 1307 ms 89740 KB Output is correct
15 Correct 962 ms 90128 KB Output is correct
16 Correct 748 ms 90264 KB Output is correct
17 Correct 1 ms 448 KB Output is correct
18 Correct 1 ms 456 KB Output is correct
19 Correct 2 ms 456 KB Output is correct
20 Correct 2 ms 668 KB Output is correct
21 Correct 2 ms 676 KB Output is correct
22 Correct 2 ms 656 KB Output is correct
23 Correct 4 ms 680 KB Output is correct
24 Correct 2 ms 676 KB Output is correct
25 Correct 1 ms 584 KB Output is correct
26 Correct 1 ms 840 KB Output is correct
27 Correct 22 ms 1224 KB Output is correct
28 Correct 19 ms 1352 KB Output is correct
29 Correct 23 ms 1352 KB Output is correct
30 Correct 16 ms 1352 KB Output is correct
31 Correct 20 ms 1352 KB Output is correct
32 Correct 0 ms 456 KB Output is correct
33 Correct 44 ms 50712 KB Output is correct
34 Correct 78 ms 89348 KB Output is correct
35 Correct 74 ms 89456 KB Output is correct
36 Correct 80 ms 89364 KB Output is correct
37 Correct 82 ms 89836 KB Output is correct
38 Correct 82 ms 90176 KB Output is correct
39 Correct 1 ms 456 KB Output is correct
40 Correct 1 ms 456 KB Output is correct
41 Correct 1 ms 456 KB Output is correct
42 Correct 302 ms 39668 KB Output is correct
43 Correct 942 ms 89388 KB Output is correct
44 Correct 634 ms 14024 KB Output is correct
45 Correct 1029 ms 89372 KB Output is correct
46 Correct 550 ms 29592 KB Output is correct
47 Correct 939 ms 89368 KB Output is correct
48 Correct 835 ms 89448 KB Output is correct
49 Correct 1063 ms 89496 KB Output is correct
50 Correct 1079 ms 89472 KB Output is correct
51 Correct 919 ms 89420 KB Output is correct
52 Correct 1099 ms 89732 KB Output is correct
53 Correct 1028 ms 90136 KB Output is correct
54 Correct 812 ms 90156 KB Output is correct
55 Correct 1 ms 456 KB Output is correct
56 Runtime error 204 ms 179128 KB Execution killed with signal 6
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 204 ms 70808 KB Output is correct
4 Correct 1312 ms 89448 KB Output is correct
5 Correct 1273 ms 44080 KB Output is correct
6 Correct 1433 ms 89452 KB Output is correct
7 Correct 1118 ms 60240 KB Output is correct
8 Correct 1288 ms 89480 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Runtime error 3 ms 912 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -