제출 #716719

#제출 시각아이디문제언어결과실행 시간메모리
716719aryan12밀림 점프 (APIO21_jumps)C++17
27 / 100
1303 ms79744 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> seg[MAXN * 4]; // at position i stores the value H[i] vector<int> H, REV; int N; void Build(int left, int right, int pos) { if(left == right) { seg[pos].push_back(H[left]); return; } int mid = (left + right) / 2; Build(left, mid, pos * 2); Build(mid + 1, right, pos * 2 + 1); merge(seg[pos * 2].begin(), seg[pos * 2].end(), seg[pos * 2 + 1].begin(), seg[pos * 2 + 1].end(), back_inserter(seg[pos])); } int Query(int l, int r, int pos, int ql, int qr, int qval) { // cout << "qpos = " << ql << ", " << qr << ", qval = " << qval << "\n"; if(ql > r || l > qr) { return -1; } if(ql <= l && r <= qr) { int cur_pos = lower_bound(seg[pos].begin(), seg[pos].end(), qval) - seg[pos].begin() - 1; if(cur_pos == -1) { return -1; } return seg[pos][cur_pos]; } int mid = (l + r) >> 1; return max(Query(l, mid, pos * 2, ql, qr, qval), Query(mid + 1, r, pos * 2 + 1, ql, qr, qval)); } void init(int n, std::vector<int> h) { stack<int> s; N = n; REV.resize(N + 1); for(int i = 0; i < h.size(); i++) { H.push_back(h[i]); REV[H[i]] = i; } Build(0, N - 1, 1); 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_min[0][i] == -1 || (dp_max[0][i] != -1 && H[dp_max[0][i]] < H[dp_min[0][i]])) { 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 // cout << "---- ---- ---- ---- ----\n"; // cout << "A = " << A << ", B = " << B << "\n"; int query_result = Query(0, N - 1, 1, A, B, H[C]); // cout << "query_result = " << query_result << "\n"; if(query_result == -1) { return -1; } A = REV[query_result]; B = A; // cout << "A = " << A << ", B = " << B << "\n"; // cout << "---- ---- ---- ---- ----\n"; 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:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     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...