oj.uz

Submission #973514

# Submission time Handle Problem Language Result Execution time Memory
973514 2024-05-02T06:16:39 Z Tuanlinh123 Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 13 ms 49668 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=1; i<=n; i++) sp[0][i]=H[i];
    for (ll i=1; i<20; i++)
        for (ll j=1; j+(1<<i)<=n+1; 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; 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>=1; 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++;
    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 (check(Max[i][B], C, D) && Max[i][B]<C)
            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];
    if (R[0][B]<C || R[0][B]>D) return -1;
    return ans+1;
}

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 49496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 49496 KB Output is correct
2 Incorrect 6 ms 49668 KB Output isn't correct
3 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 Incorrect 6 ms 49668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49496 KB Output is correct
2 Incorrect 6 ms 49656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 49496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 49496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 49496 KB Output isn't correct
2 Halted 0 ms 0 KB -