제출 #973521

#제출 시각아이디문제언어결과실행 시간메모리
973521Tuanlinh123밀림 점프 (APIO21_jumps)C++17
48 / 100
919 ms64532 KiB
// #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; 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 -1; return ans+1; }

컴파일 시 표준 에러 (stderr) 메시지

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;
      |                              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...