제출 #1022358

#제출 시각아이디문제언어결과실행 시간메모리
1022358MohamedFaresNebili밀림 점프 (APIO21_jumps)C++14
21 / 100
230 ms51264 KiB
#include <bits/stdc++.h> using namespace std; int N; vector<int> H; int L[100005][20], R[100005][20], UP[100005][20]; void init(int _N, vector<int> _H) { N = _N, swap(H, _H); H.push_back(0); for(int l = 0; l <= N; l++) L[l][0] = R[l][0] = UP[l][0] = N; stack<int> ST; for(int l = 0; l < N; l++) { while(!ST.empty() && H[ST.top()] < H[l]) ST.pop(); if(!ST.empty()) L[l][0] = ST.top(); ST.push(l); } while(!ST.empty()) ST.pop(); for(int l = N - 1; l >= 0; l--) { while(!ST.empty() && H[ST.top()] < H[l]) ST.pop(); if(!ST.empty()) R[l][0] = ST.top(); ST.push(l); } for(int l = 0; l < N; l++) UP[l][0] = (H[L[l][0]] > H[R[l][0]] ? L[l][0] : R[l][0]); for(int l = 1; l < 20; l++) for(int i = 0; i <= N; i++) L[i][l] = L[L[i][l - 1]][l - 1], R[i][l] = R[R[i][l - 1]][l - 1], UP[i][l] = UP[UP[i][l - 1]][l - 1]; } int minimum_jumps(int A, int B, int C, int D) { int ans = B; for(int l = 19; l >= 0; l--) if(L[ans][l] >= A && R[L[ans][l]][0] <= D) ans = L[ans][l]; if(R[ans][0] >= C && R[ans][0] <= D) return 1; int res = 0; for(int l = 19; l >= 0; l--) if(R[UP[ans][l]][0] < C) ans = UP[ans][l], res += (1 << l); if(R[UP[ans][0]][0] >= C && R[UP[ans][0]][0] <= D) return res + 2; for(int l = 19; l >= 0; l--) if(R[ans][l] < C) ans = R[ans][l], res += (1 << l); if(R[ans][0] >= C && R[ans][0] <= D) return res + 1; return -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...