oj.uz

Submission #567429

# Submission time Handle Problem Language Result Execution time Memory
567429 2022-05-23T12:50:00 Z Mazaalai Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1228 ms 57496 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair <ll, ll>;
int n;
const int N = 2e5 + 5;
const int M = 20;
const int INF = 1e6;
int nums[N], L[N], R[N];
vector <int> paths[N];
bool test1;
int pos[N];
int maxi[N][M];
int nx[N][M];
int greedy[N][M];
int A, B, C, D;
// int getRight(int pos, )
int getMax(int l, int r) {
    int p = 0;
    while(l + (1<<(p+1)) - 1 <= r) p++;
    return max(maxi[l][p], maxi[r - (1<<p) + 1][p]);
}
void init(int _n, vector<int> _nums) {
    test1 = 1;
    n = _n;
    nums[0] = nums[n+1] = INF;
    for (int i = 0; i < n; i++) test1 &= (_nums[i] == i+1);
    for (int i = 1; i <= n; i++) {
        maxi[i][0] = nums[i] = _nums[i-1];
        pos[nums[i]] = i;
    }
    L[0] = R[0] = 0;
    L[n+1] = R[n+1] = n+1;
    stack <int> stk;
    stk.push(0);
    for (int i = 1; i <= n; i++) {
        while(nums[stk.top()] < nums[i]) stk.pop();
        L[i] = stk.top();
        stk.push(i);
    }
    while(!stk.empty()) stk.pop();
    stk.push(n+1);
    for (int i = n; i > 0; i--) {
        while(nums[stk.top()] < nums[i]) stk.pop();
        R[i] = stk.top();
        stk.push(i);
    }
    for (int i = 1; i <= n; i++) {
        int a = L[i], b = R[i];
        nx[i][0] = b;
        if (nums[a] == INF) swap(a, b);
        if (nums[a] == INF) greedy[i][0] = i;
        if (nums[a] < nums[b] && nums[b] != INF) a = b;
        greedy[i][0] = a;
    }
    for (int j = 1; j < M; j++)
    for (int i = 1; i <= n; i++) {
        maxi[i][j] = max(maxi[i][j-1], maxi[min(n, i+(1<<(j-1)))][j-1]);
        nx[i][j] = nx[nx[i][j-1]][j-1];
        greedy[i][j] = greedy[greedy[i][j-1]][j-1];
    }
    // for (int i = 1; i <= n; i++) 
    // for (int j = i; j <= n; j++) cout << i << ',' << j << ": " << getMax(i, j) << '\n';
}
int minimum_jumps(int _A, int _B, int _C, int _D) {
    A = 1 + _A;
    B = 1 + _B;
    C = 1 + _C;
    D = 1 + _D;
    if (B+1 == C) return (nums[B] > getMax(C, D) ? -1 : 1);
    int x = getMax(A, B);
    int y = getMax(B+1, C-1);
    int z = getMax(C, D);
    if (y > z) return -1;
    if (nums[B] > z) return -1;
    int res = 0;
    if (x < y) { // 1 2 3
        int p = pos[x];
        for (int i = M-1; i >= 0; i--) {
            if (nums[greedy[p][i]] < y) {
                res += (1<<i);
                p = greedy[p][i];
            }
        }
        if (y <= nums[greedy[p][0]] && nums[greedy[p][0]] <= z) return res + 2;
        for (int i = M-1; i >= 0; i--) {
            if (nums[nx[p][i]] <= y) {
                res += (1<<i);
                p = nx[p][i];
            }
        }
        return res+1;
    } else if (x < z) { // 2 1 3
        return 1;
    } else if (x > z) { // 3 1 2
        int l = A, r = B, p = r;
        while (l <= r) {
            int mid = (l+r)>>1;
            int tmp = getMax(mid, B);
            if (tmp > y && tmp < z) return 1;
            if (tmp > z) {
                l = mid+1;
            } else {
                p = min(p, mid);
                r = mid-1;
            }
        }
        for (int i = M-1; i >= 0; i--) {
            if (nums[nx[p][i]] <= y) {
                res += (1<<i);
                p = nx[p][i];
            }
        }
        return res + 1;
    }
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:118:1: warning: control reaches end of non-void function [-Wreturn-type]
  118 | }
      | ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 210 ms 46792 KB Output is correct
4 Correct 927 ms 57464 KB Output is correct
5 Correct 938 ms 31388 KB Output is correct
6 Correct 1057 ms 57484 KB Output is correct
7 Correct 833 ms 40884 KB Output is correct
8 Correct 1079 ms 57392 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 4 ms 4984 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 5 ms 4944 KB Output is correct
6 Incorrect 5 ms 5072 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 4 ms 4984 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 5 ms 4944 KB Output is correct
6 Incorrect 5 ms 5072 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 107 ms 46584 KB Output is correct
6 Correct 112 ms 56704 KB Output is correct
7 Correct 69 ms 31432 KB Output is correct
8 Correct 131 ms 56520 KB Output is correct
9 Correct 15 ms 12752 KB Output is correct
10 Correct 126 ms 56648 KB Output is correct
11 Correct 132 ms 57432 KB Output is correct
12 Incorrect 129 ms 57220 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 215 ms 28592 KB Output is correct
5 Correct 886 ms 56704 KB Output is correct
6 Correct 471 ms 13520 KB Output is correct
7 Correct 974 ms 56652 KB Output is correct
8 Correct 488 ms 22728 KB Output is correct
9 Correct 1020 ms 56660 KB Output is correct
10 Correct 1228 ms 57480 KB Output is correct
11 Correct 1096 ms 57344 KB Output is correct
12 Correct 976 ms 57360 KB Output is correct
13 Correct 1109 ms 56544 KB Output is correct
14 Correct 797 ms 56932 KB Output is correct
15 Correct 892 ms 57484 KB Output is correct
16 Correct 904 ms 57476 KB Output is correct
17 Correct 4 ms 4944 KB Output is correct
18 Correct 3 ms 4944 KB Output is correct
19 Correct 4 ms 4944 KB Output is correct
20 Correct 5 ms 5072 KB Output is correct
21 Correct 5 ms 5072 KB Output is correct
22 Correct 5 ms 5072 KB Output is correct
23 Correct 5 ms 5072 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 3 ms 5072 KB Output is correct
26 Correct 3 ms 5200 KB Output is correct
27 Correct 21 ms 5456 KB Output is correct
28 Correct 21 ms 5456 KB Output is correct
29 Correct 27 ms 5456 KB Output is correct
30 Correct 20 ms 5456 KB Output is correct
31 Correct 22 ms 5456 KB Output is correct
32 Correct 3 ms 4944 KB Output is correct
33 Correct 65 ms 34848 KB Output is correct
34 Correct 117 ms 56648 KB Output is correct
35 Correct 113 ms 57348 KB Output is correct
36 Correct 129 ms 56600 KB Output is correct
37 Correct 144 ms 56912 KB Output is correct
38 Correct 119 ms 57496 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 215 ms 28592 KB Output is correct
5 Correct 886 ms 56704 KB Output is correct
6 Correct 471 ms 13520 KB Output is correct
7 Correct 974 ms 56652 KB Output is correct
8 Correct 488 ms 22728 KB Output is correct
9 Correct 1020 ms 56660 KB Output is correct
10 Correct 1228 ms 57480 KB Output is correct
11 Correct 1096 ms 57344 KB Output is correct
12 Correct 976 ms 57360 KB Output is correct
13 Correct 1109 ms 56544 KB Output is correct
14 Correct 797 ms 56932 KB Output is correct
15 Correct 892 ms 57484 KB Output is correct
16 Correct 904 ms 57476 KB Output is correct
17 Correct 4 ms 4944 KB Output is correct
18 Correct 3 ms 4944 KB Output is correct
19 Correct 4 ms 4944 KB Output is correct
20 Correct 5 ms 5072 KB Output is correct
21 Correct 5 ms 5072 KB Output is correct
22 Correct 5 ms 5072 KB Output is correct
23 Correct 5 ms 5072 KB Output is correct
24 Correct 4 ms 5072 KB Output is correct
25 Correct 3 ms 5072 KB Output is correct
26 Correct 3 ms 5200 KB Output is correct
27 Correct 21 ms 5456 KB Output is correct
28 Correct 21 ms 5456 KB Output is correct
29 Correct 27 ms 5456 KB Output is correct
30 Correct 20 ms 5456 KB Output is correct
31 Correct 22 ms 5456 KB Output is correct
32 Correct 3 ms 4944 KB Output is correct
33 Correct 65 ms 34848 KB Output is correct
34 Correct 117 ms 56648 KB Output is correct
35 Correct 113 ms 57348 KB Output is correct
36 Correct 129 ms 56600 KB Output is correct
37 Correct 144 ms 56912 KB Output is correct
38 Correct 119 ms 57496 KB Output is correct
39 Correct 3 ms 4944 KB Output is correct
40 Correct 4 ms 4944 KB Output is correct
41 Correct 3 ms 4944 KB Output is correct
42 Correct 200 ms 28536 KB Output is correct
43 Correct 846 ms 56648 KB Output is correct
44 Correct 551 ms 13440 KB Output is correct
45 Correct 837 ms 56520 KB Output is correct
46 Correct 498 ms 22728 KB Output is correct
47 Correct 744 ms 56656 KB Output is correct
48 Correct 763 ms 57476 KB Output is correct
49 Correct 1149 ms 57336 KB Output is correct
50 Correct 1114 ms 57380 KB Output is correct
51 Correct 788 ms 56580 KB Output is correct
52 Correct 871 ms 57164 KB Output is correct
53 Correct 854 ms 57476 KB Output is correct
54 Correct 858 ms 57476 KB Output is correct
55 Correct 3 ms 4944 KB Output is correct
56 Incorrect 162 ms 56464 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 210 ms 46792 KB Output is correct
4 Correct 927 ms 57464 KB Output is correct
5 Correct 938 ms 31388 KB Output is correct
6 Correct 1057 ms 57484 KB Output is correct
7 Correct 833 ms 40884 KB Output is correct
8 Correct 1079 ms 57392 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 4 ms 4984 KB Output is correct
11 Correct 3 ms 4944 KB Output is correct
12 Correct 2 ms 4944 KB Output is correct
13 Correct 5 ms 4944 KB Output is correct
14 Incorrect 5 ms 5072 KB Output isn't correct
15 Halted 0 ms 0 KB -