oj.uz

답안 #973523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973523 2024-05-02T06:36:38 Z Tuanlinh123 밀림 점프 (APIO21_jumps) C++17
48 / 100
 902 ms 64672 KB 
// #include "stub.cpp"
#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++;
    for (ll i=19; i>=0; i--)
        if (check(L[i][B], C, D) && L[i][B]>=A)
            B=L[i][B];
    // cout << "after left jumps: " << B << endl;
    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];
    // cout << "after max jumps: " << B << endl;
    if (Max[0][B]>=C && Max[0][B]<=D) return ans+1;
    for (ll i=19; i>=0; i--)
        if (R[i][B]<C)
            ans+=1<<i, B=R[i][B];
    // cout << "after right jumps: " << B << endl;
    if (R[0][B]>=C && R[0][B]<=D) return ans+1;
    return -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
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 112 ms 63940 KB Output is correct
4 Correct 887 ms 64560 KB Output is correct
5 Correct 728 ms 61340 KB Output is correct
6 Correct 814 ms 64320 KB Output is correct
7 Correct 665 ms 63788 KB Output is correct
8 Correct 837 ms 64544 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 6 ms 49600 KB Output is correct
4 Correct 7 ms 49496 KB Output is correct
5 Correct 7 ms 51544 KB Output is correct
6 Incorrect 7 ms 53800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 6 ms 49600 KB Output is correct
4 Correct 7 ms 49496 KB Output is correct
5 Correct 7 ms 51544 KB Output is correct
6 Incorrect 7 ms 53800 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 7 ms 49752 KB Output is correct
4 Correct 5 ms 49496 KB Output is correct
5 Correct 29 ms 63424 KB Output is correct
6 Correct 35 ms 63684 KB Output is correct
7 Correct 20 ms 60928 KB Output is correct
8 Correct 40 ms 63676 KB Output is correct
9 Correct 11 ms 60200 KB Output is correct
10 Correct 35 ms 63676 KB Output is correct
11 Correct 40 ms 64428 KB Output is correct
12 Correct 31 ms 64176 KB Output is correct
13 Correct 35 ms 64172 KB Output is correct
14 Correct 35 ms 63496 KB Output is correct
15 Incorrect 37 ms 63912 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 6 ms 49496 KB Output is correct
4 Correct 170 ms 60844 KB Output is correct
5 Correct 809 ms 63552 KB Output is correct
6 Correct 450 ms 60116 KB Output is correct
7 Correct 773 ms 63664 KB Output is correct
8 Correct 430 ms 60616 KB Output is correct
9 Correct 745 ms 63684 KB Output is correct
10 Correct 811 ms 64504 KB Output is correct
11 Correct 865 ms 64508 KB Output is correct
12 Correct 783 ms 64432 KB Output is correct
13 Correct 748 ms 63684 KB Output is correct
14 Correct 837 ms 63976 KB Output is correct
15 Correct 768 ms 64448 KB Output is correct
16 Correct 757 ms 64440 KB Output is correct
17 Correct 6 ms 49496 KB Output is correct
18 Correct 6 ms 49640 KB Output is correct
19 Correct 6 ms 49496 KB Output is correct
20 Correct 8 ms 53592 KB Output is correct
21 Correct 7 ms 53592 KB Output is correct
22 Correct 7 ms 53740 KB Output is correct
23 Correct 7 ms 53592 KB Output is correct
24 Correct 7 ms 53592 KB Output is correct
25 Correct 6 ms 53592 KB Output is correct
26 Correct 6 ms 55828 KB Output is correct
27 Correct 19 ms 55640 KB Output is correct
28 Correct 16 ms 55640 KB Output is correct
29 Correct 16 ms 55640 KB Output is correct
30 Correct 16 ms 55640 KB Output is correct
31 Correct 15 ms 55640 KB Output is correct
32 Correct 5 ms 49496 KB Output is correct
33 Correct 23 ms 63076 KB Output is correct
34 Correct 35 ms 63484 KB Output is correct
35 Correct 32 ms 64636 KB Output is correct
36 Correct 34 ms 63660 KB Output is correct
37 Correct 32 ms 63980 KB Output is correct
38 Correct 31 ms 64672 KB Output is correct

Subtask #6
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 6 ms 49496 KB Output is correct
4 Correct 170 ms 60844 KB Output is correct
5 Correct 809 ms 63552 KB Output is correct
6 Correct 450 ms 60116 KB Output is correct
7 Correct 773 ms 63664 KB Output is correct
8 Correct 430 ms 60616 KB Output is correct
9 Correct 745 ms 63684 KB Output is correct
10 Correct 811 ms 64504 KB Output is correct
11 Correct 865 ms 64508 KB Output is correct
12 Correct 783 ms 64432 KB Output is correct
13 Correct 748 ms 63684 KB Output is correct
14 Correct 837 ms 63976 KB Output is correct
15 Correct 768 ms 64448 KB Output is correct
16 Correct 757 ms 64440 KB Output is correct
17 Correct 6 ms 49496 KB Output is correct
18 Correct 6 ms 49640 KB Output is correct
19 Correct 6 ms 49496 KB Output is correct
20 Correct 8 ms 53592 KB Output is correct
21 Correct 7 ms 53592 KB Output is correct
22 Correct 7 ms 53740 KB Output is correct
23 Correct 7 ms 53592 KB Output is correct
24 Correct 7 ms 53592 KB Output is correct
25 Correct 6 ms 53592 KB Output is correct
26 Correct 6 ms 55828 KB Output is correct
27 Correct 19 ms 55640 KB Output is correct
28 Correct 16 ms 55640 KB Output is correct
29 Correct 16 ms 55640 KB Output is correct
30 Correct 16 ms 55640 KB Output is correct
31 Correct 15 ms 55640 KB Output is correct
32 Correct 5 ms 49496 KB Output is correct
33 Correct 23 ms 63076 KB Output is correct
34 Correct 35 ms 63484 KB Output is correct
35 Correct 32 ms 64636 KB Output is correct
36 Correct 34 ms 63660 KB Output is correct
37 Correct 32 ms 63980 KB Output is correct
38 Correct 31 ms 64672 KB Output is correct
39 Correct 6 ms 49496 KB Output is correct
40 Correct 5 ms 49496 KB Output is correct
41 Correct 5 ms 49496 KB Output is correct
42 Correct 194 ms 60816 KB Output is correct
43 Correct 787 ms 63676 KB Output is correct
44 Correct 485 ms 60116 KB Output is correct
45 Correct 784 ms 63680 KB Output is correct
46 Correct 426 ms 60604 KB Output is correct
47 Correct 776 ms 63676 KB Output is correct
48 Correct 815 ms 64444 KB Output is correct
49 Correct 770 ms 64256 KB Output is correct
50 Correct 827 ms 64424 KB Output is correct
51 Correct 765 ms 63684 KB Output is correct
52 Correct 900 ms 63976 KB Output is correct
53 Correct 714 ms 64428 KB Output is correct
54 Correct 774 ms 64428 KB Output is correct
55 Correct 6 ms 49496 KB Output is correct
56 Correct 75 ms 63684 KB Output is correct
57 Correct 772 ms 63680 KB Output is correct
58 Correct 338 ms 60312 KB Output is correct
59 Correct 739 ms 63680 KB Output is correct
60 Correct 327 ms 60440 KB Output is correct
61 Correct 771 ms 63680 KB Output is correct
62 Correct 816 ms 64444 KB Output is correct
63 Correct 821 ms 64200 KB Output is correct
64 Correct 779 ms 64196 KB Output is correct
65 Correct 769 ms 63660 KB Output is correct
66 Correct 902 ms 64180 KB Output is correct
67 Correct 692 ms 64444 KB Output is correct
68 Correct 780 ms 64428 KB Output is correct
69 Correct 5 ms 49496 KB Output is correct
70 Correct 6 ms 51544 KB Output is correct
71 Correct 7 ms 53592 KB Output is correct
72 Correct 7 ms 53592 KB Output is correct
73 Correct 7 ms 53592 KB Output is correct
74 Correct 7 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 49644 KB Output is correct
78 Correct 7 ms 49688 KB Output is correct
79 Correct 7 ms 53848 KB Output is correct
80 Correct 7 ms 53592 KB Output is correct
81 Correct 7 ms 53592 KB Output is correct
82 Correct 7 ms 53592 KB Output is correct
83 Correct 7 ms 53740 KB Output is correct
84 Correct 7 ms 53592 KB Output is correct
85 Correct 8 ms 53740 KB Output is correct
86 Correct 16 ms 55640 KB Output is correct
87 Correct 16 ms 55640 KB Output is correct
88 Correct 15 ms 55640 KB Output is correct
89 Correct 19 ms 55640 KB Output is correct
90 Correct 17 ms 55648 KB Output is correct
91 Correct 6 ms 53592 KB Output is correct
92 Correct 7 ms 55796 KB Output is correct
93 Correct 19 ms 55640 KB Output is correct
94 Correct 15 ms 55640 KB Output is correct
95 Correct 15 ms 55640 KB Output is correct
96 Correct 16 ms 55856 KB Output is correct
97 Correct 16 ms 55640 KB Output is correct
98 Correct 6 ms 49492 KB Output is correct
99 Correct 35 ms 63676 KB Output is correct
100 Correct 38 ms 63656 KB Output is correct
101 Correct 34 ms 64520 KB Output is correct
102 Correct 35 ms 63664 KB Output is correct
103 Correct 35 ms 64064 KB Output is correct
104 Correct 36 ms 64444 KB Output is correct
105 Correct 6 ms 49496 KB Output is correct
106 Correct 23 ms 63020 KB Output is correct
107 Correct 40 ms 63928 KB Output is correct
108 Correct 31 ms 64448 KB Output is correct
109 Correct 34 ms 63732 KB Output is correct
110 Correct 33 ms 63932 KB Output is correct
111 Correct 32 ms 64456 KB Output is correct

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 49496 KB Output is correct
2 Correct 6 ms 49496 KB Output is correct
3 Correct 112 ms 63940 KB Output is correct
4 Correct 887 ms 64560 KB Output is correct
5 Correct 728 ms 61340 KB Output is correct
6 Correct 814 ms 64320 KB Output is correct
7 Correct 665 ms 63788 KB Output is correct
8 Correct 837 ms 64544 KB Output is correct
9 Correct 6 ms 49496 KB Output is correct
10 Correct 6 ms 49496 KB Output is correct
11 Correct 6 ms 49600 KB Output is correct
12 Correct 7 ms 49496 KB Output is correct
13 Correct 7 ms 51544 KB Output is correct
14 Incorrect 7 ms 53800 KB Output isn't correct
15 Halted 0 ms 0 KB -