제출 #716714

#제출 시각아이디문제언어결과실행 시간메모리
716714aryan12밀림 점프 (APIO21_jumps)C++17
0 / 100
165 ms26628 KiB
#include "jumps.h" #include <bits/stdc++.h> #include <vector> using namespace std; const int MAXN = 2e5 + 5; int dp_min[19][MAXN], dp_max[19][MAXN]; vector<int> H; int N; void init(int n, std::vector<int> h) { stack<int> s; N = n; for(int i = 0; i < h.size(); i++) { H.push_back(h[i]); } for(int i = 0; i < N; i++) { while(!s.empty() && H[s.top()] < H[i]) { s.pop(); } if(s.empty()) { dp_min[0][i] = -1; } else { dp_min[0][i] = s.top(); } s.push(i); } while(!s.empty()) { s.pop(); } for(int i = N - 1; i >= 0; i--) { while(!s.empty() && H[s.top()] < H[i]) { s.pop(); } if(s.empty()) { dp_max[0][i] = -1; } else { dp_max[0][i] = s.top(); } s.push(i); if((dp_max[0][i] < dp_min[0][i] && dp_max[0][i] != -1) || (dp_min[0][i] == -1)) { swap(dp_min[0][i], dp_max[0][i]); } } for(int i = 1; i < 19; i++) { for(int j = 0; j < N; j++) { dp_min[i][j] = (dp_min[i - 1][j] == -1) ? -1 : dp_min[i - 1][dp_min[i - 1][j]]; dp_max[i][j] = (dp_max[i - 1][j] == -1) ? -1 : dp_max[i - 1][dp_max[i - 1][j]]; assert(dp_max[i][j] == -1 || H[dp_max[i][j]] >= H[dp_min[i][j]]); } } } int minimum_jumps(int A, int B, int C, int D) { // A = B && C = D int ans = 0; for(int i = 18; i >= 0; i--) { if(dp_max[i][A] != -1 && H[dp_max[i][A]] <= H[C]) { ans += (1 << i); A = dp_max[i][A]; } } for(int i = 18; i >= 0; i--) { if(dp_min[i][A] != -1 && H[dp_min[i][A]] <= H[C]) { ans += (1 << i); A = dp_min[i][A]; } } if(H[A] != H[C]) { return -1; } return ans; }

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

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0; i < h.size(); i++)
      |                    ~~^~~~~~~~~~
#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...