oj.uz

Submission #973524

# Submission time Handle Problem Language Result Execution time Memory
973524 2024-05-02T06:42:49 Z Tuanlinh123 Rainforest Jumps (APIO21_jumps) C++17
48 / 100
 922 ms 64584 KB 
#include "jumps.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=200005, inf=1e9;
ll n, sp[20][maxn];
ll L[20][maxn], R[20][maxn], Max[20][maxn];

void init(ll N, vector<ll> H) 
{
    n=N, H.insert(H.begin(), inf), H.insert(H.end(), inf);
    for (ll i=0; i<=n+1; i++) sp[0][i]=H[i];
    for (ll i=1; i<20; i++)
        for (ll j=0; j+(1<<i)<=n+2; j++)
            sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
    stack <ll> st; st.push(0), L[0][0]=0;
    for (ll i=1; i<=n+1; i++)
    {
        while (H[st.top()]<H[i]) st.pop();
        L[0][i]=st.top(), st.push(i);
    }
    while (sz(st)) st.pop(); st.push(n+1), R[0][n+1]=n+1;
    for (ll i=n; i>=0; i--)
    {
        while (H[st.top()]<H[i]) st.pop();
        R[0][i]=st.top(), st.push(i);
    }
    for (ll i=0; i<=n+1; i++)
        Max[0][i]=H[L[0][i]]>H[R[0][i]]?L[0][i]:R[0][i];
    for (ll i=1; i<20; i++)
        for (ll j=0; j<=n+1; j++)
        {
            L[i][j]=L[i-1][L[i-1][j]];
            R[i][j]=R[i-1][R[i-1][j]];
            Max[i][j]=Max[i-1][Max[i-1][j]];
        }
}

ll query(ll l, ll r)
{
    ll j=__lg(r-l+1);
    return max(sp[j][l], sp[j][r-(1<<j)+1]);
}
bool check(ll i, ll l, ll r) {return query(i, r)==query(l, r);}

int minimum_jumps(int A, int B, int C, int D) 
{
    A++, B++, C++, D++;
    if (!check(B, C, D)) return -1;
    ll ans1=0;
    for (ll i=19, cr=B; i>=0; i--)
        if (R[i][cr]<C) 
            ans1+=1<<i, cr=R[i][cr];
    for (ll i=19; i>=0; i--)
        if (check(L[i][B], C, D) && L[i][B]>=A)
            B=L[i][B];
    ll ans=0;
    for (ll i=19; i>=0; i--)
        if (Max[i][B]<C && check(Max[i][B], C, D))
            ans+=1<<i, B=Max[i][B];
    for (ll i=19; i>=0; i--)
        if (R[i][B]<C)
            ans+=1<<i, B=R[i][B];
    return min(ans1, ans)+1;
}

Compilation message

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:23:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |             sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
      |                                                    ~^~
jumps.cpp:30:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   30 |     while (sz(st)) st.pop(); st.push(n+1), R[0][n+1]=n+1;
      |     ^~~~~
jumps.cpp:30:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   30 |     while (sz(st)) st.pop(); st.push(n+1), R[0][n+1]=n+1;
      |                              ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49496 KB Output is correct
2 Correct 7 ms 49496 KB Output is correct
3 Correct 126 ms 63924 KB Output is correct
4 Correct 817 ms 64576 KB Output is correct
5 Correct 708 ms 61128 KB Output is correct
6 Correct 862 ms 64444 KB Output is correct
7 Correct 654 ms 63792 KB Output is correct
8 Correct 822 ms 64448 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 5 ms 49624 KB Output is correct
4 Correct 6 ms 49496 KB Output is correct
5 Correct 6 ms 51544 KB Output is correct
6 Correct 7 ms 53592 KB Output is correct
7 Correct 6 ms 53592 KB Output is correct
8 Correct 7 ms 53592 KB Output is correct
9 Incorrect 6 ms 53592 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 5 ms 49624 KB Output is correct
4 Correct 6 ms 49496 KB Output is correct
5 Correct 6 ms 51544 KB Output is correct
6 Correct 7 ms 53592 KB Output is correct
7 Correct 6 ms 53592 KB Output is correct
8 Correct 7 ms 53592 KB Output is correct
9 Incorrect 6 ms 53592 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49492 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 6 ms 49496 KB Output is correct
4 Correct 6 ms 49496 KB Output is correct
5 Correct 30 ms 63364 KB Output is correct
6 Correct 36 ms 63484 KB Output is correct
7 Correct 20 ms 60912 KB Output is correct
8 Correct 38 ms 63896 KB Output is correct
9 Correct 11 ms 60200 KB Output is correct
10 Correct 35 ms 63680 KB Output is correct
11 Correct 35 ms 64444 KB Output is correct
12 Correct 31 ms 64188 KB Output is correct
13 Correct 40 ms 64280 KB Output is correct
14 Correct 34 ms 63688 KB Output is correct
15 Incorrect 32 ms 63940 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 49496 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 6 ms 49496 KB Output is correct
4 Correct 133 ms 60840 KB Output is correct
5 Correct 599 ms 63656 KB Output is correct
6 Correct 399 ms 60116 KB Output is correct
7 Correct 606 ms 63672 KB Output is correct
8 Correct 345 ms 60488 KB Output is correct
9 Correct 595 ms 63684 KB Output is correct
10 Correct 862 ms 64444 KB Output is correct
11 Correct 789 ms 64448 KB Output is correct
12 Correct 772 ms 64452 KB Output is correct
13 Correct 594 ms 63664 KB Output is correct
14 Correct 906 ms 63932 KB Output is correct
15 Correct 645 ms 64448 KB Output is correct
16 Correct 597 ms 64432 KB Output is correct
17 Correct 5 ms 49496 KB Output is correct
18 Correct 5 ms 49748 KB Output is correct
19 Correct 6 ms 49496 KB Output is correct
20 Correct 7 ms 53592 KB Output is correct
21 Correct 7 ms 53592 KB Output is correct
22 Correct 6 ms 53592 KB Output is correct
23 Correct 7 ms 53592 KB Output is correct
24 Correct 6 ms 53788 KB Output is correct
25 Correct 6 ms 53592 KB Output is correct
26 Correct 6 ms 55640 KB Output is correct
27 Correct 16 ms 55640 KB Output is correct
28 Correct 15 ms 55640 KB Output is correct
29 Correct 14 ms 55892 KB Output is correct
30 Correct 15 ms 55640 KB Output is correct
31 Correct 14 ms 55640 KB Output is correct
32 Correct 6 ms 49496 KB Output is correct
33 Correct 22 ms 62920 KB Output is correct
34 Correct 36 ms 63664 KB Output is correct
35 Correct 33 ms 64240 KB Output is correct
36 Correct 40 ms 63736 KB Output is correct
37 Correct 36 ms 63940 KB Output is correct
38 Correct 32 ms 64504 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 49496 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 6 ms 49496 KB Output is correct
4 Correct 133 ms 60840 KB Output is correct
5 Correct 599 ms 63656 KB Output is correct
6 Correct 399 ms 60116 KB Output is correct
7 Correct 606 ms 63672 KB Output is correct
8 Correct 345 ms 60488 KB Output is correct
9 Correct 595 ms 63684 KB Output is correct
10 Correct 862 ms 64444 KB Output is correct
11 Correct 789 ms 64448 KB Output is correct
12 Correct 772 ms 64452 KB Output is correct
13 Correct 594 ms 63664 KB Output is correct
14 Correct 906 ms 63932 KB Output is correct
15 Correct 645 ms 64448 KB Output is correct
16 Correct 597 ms 64432 KB Output is correct
17 Correct 5 ms 49496 KB Output is correct
18 Correct 5 ms 49748 KB Output is correct
19 Correct 6 ms 49496 KB Output is correct
20 Correct 7 ms 53592 KB Output is correct
21 Correct 7 ms 53592 KB Output is correct
22 Correct 6 ms 53592 KB Output is correct
23 Correct 7 ms 53592 KB Output is correct
24 Correct 6 ms 53788 KB Output is correct
25 Correct 6 ms 53592 KB Output is correct
26 Correct 6 ms 55640 KB Output is correct
27 Correct 16 ms 55640 KB Output is correct
28 Correct 15 ms 55640 KB Output is correct
29 Correct 14 ms 55892 KB Output is correct
30 Correct 15 ms 55640 KB Output is correct
31 Correct 14 ms 55640 KB Output is correct
32 Correct 6 ms 49496 KB Output is correct
33 Correct 22 ms 62920 KB Output is correct
34 Correct 36 ms 63664 KB Output is correct
35 Correct 33 ms 64240 KB Output is correct
36 Correct 40 ms 63736 KB Output is correct
37 Correct 36 ms 63940 KB Output is correct
38 Correct 32 ms 64504 KB Output is correct
39 Correct 7 ms 49752 KB Output is correct
40 Correct 5 ms 49496 KB Output is correct
41 Correct 5 ms 49592 KB Output is correct
42 Correct 154 ms 61084 KB Output is correct
43 Correct 597 ms 63676 KB Output is correct
44 Correct 411 ms 60116 KB Output is correct
45 Correct 598 ms 63672 KB Output is correct
46 Correct 315 ms 60488 KB Output is correct
47 Correct 636 ms 63748 KB Output is correct
48 Correct 863 ms 64444 KB Output is correct
49 Correct 788 ms 64436 KB Output is correct
50 Correct 860 ms 64448 KB Output is correct
51 Correct 605 ms 63676 KB Output is correct
52 Correct 922 ms 63912 KB Output is correct
53 Correct 676 ms 64428 KB Output is correct
54 Correct 613 ms 64568 KB Output is correct
55 Correct 8 ms 49496 KB Output is correct
56 Correct 61 ms 63668 KB Output is correct
57 Correct 601 ms 63656 KB Output is correct
58 Correct 313 ms 60312 KB Output is correct
59 Correct 630 ms 63504 KB Output is correct
60 Correct 259 ms 60608 KB Output is correct
61 Correct 630 ms 63668 KB Output is correct
62 Correct 880 ms 64584 KB Output is correct
63 Correct 852 ms 64260 KB Output is correct
64 Correct 778 ms 64192 KB Output is correct
65 Correct 591 ms 63664 KB Output is correct
66 Correct 912 ms 63944 KB Output is correct
67 Correct 697 ms 64524 KB Output is correct
68 Correct 585 ms 64492 KB Output is correct
69 Correct 6 ms 49496 KB Output is correct
70 Correct 6 ms 51708 KB Output is correct
71 Correct 8 ms 53592 KB Output is correct
72 Correct 7 ms 53592 KB Output is correct
73 Correct 6 ms 53696 KB Output is correct
74 Correct 8 ms 53592 KB Output is correct
75 Correct 7 ms 53592 KB Output is correct
76 Correct 6 ms 49496 KB Output is correct
77 Correct 6 ms 49496 KB Output is correct
78 Correct 7 ms 49644 KB Output is correct
79 Correct 8 ms 53592 KB Output is correct
80 Correct 9 ms 53784 KB Output is correct
81 Correct 9 ms 53844 KB Output is correct
82 Correct 8 ms 53844 KB Output is correct
83 Correct 7 ms 53592 KB Output is correct
84 Correct 6 ms 53592 KB Output is correct
85 Correct 8 ms 53744 KB Output is correct
86 Correct 14 ms 55640 KB Output is correct
87 Correct 17 ms 55876 KB Output is correct
88 Correct 15 ms 55640 KB Output is correct
89 Correct 18 ms 55712 KB Output is correct
90 Correct 17 ms 55640 KB Output is correct
91 Correct 6 ms 53592 KB Output is correct
92 Correct 6 ms 55800 KB Output is correct
93 Correct 14 ms 55640 KB Output is correct
94 Correct 15 ms 55640 KB Output is correct
95 Correct 17 ms 55640 KB Output is correct
96 Correct 18 ms 55640 KB Output is correct
97 Correct 14 ms 55640 KB Output is correct
98 Correct 5 ms 49496 KB Output is correct
99 Correct 44 ms 63904 KB Output is correct
100 Correct 35 ms 63676 KB Output is correct
101 Correct 32 ms 64196 KB Output is correct
102 Correct 43 ms 63660 KB Output is correct
103 Correct 40 ms 63980 KB Output is correct
104 Correct 33 ms 64548 KB Output is correct
105 Correct 6 ms 49496 KB Output is correct
106 Correct 23 ms 62828 KB Output is correct
107 Correct 35 ms 63744 KB Output is correct
108 Correct 36 ms 64424 KB Output is correct
109 Correct 37 ms 63676 KB Output is correct
110 Correct 33 ms 64120 KB Output is correct
111 Correct 35 ms 64432 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49496 KB Output is correct
2 Correct 7 ms 49496 KB Output is correct
3 Correct 126 ms 63924 KB Output is correct
4 Correct 817 ms 64576 KB Output is correct
5 Correct 708 ms 61128 KB Output is correct
6 Correct 862 ms 64444 KB Output is correct
7 Correct 654 ms 63792 KB Output is correct
8 Correct 822 ms 64448 KB Output is correct
9 Correct 7 ms 49496 KB Output is correct
10 Correct 6 ms 49496 KB Output is correct
11 Correct 5 ms 49624 KB Output is correct
12 Correct 6 ms 49496 KB Output is correct
13 Correct 6 ms 51544 KB Output is correct
14 Correct 7 ms 53592 KB Output is correct
15 Correct 6 ms 53592 KB Output is correct
16 Correct 7 ms 53592 KB Output is correct
17 Incorrect 6 ms 53592 KB Output isn't correct
18 Halted 0 ms 0 KB -