제출 #569652

#제출 시각아이디문제언어결과실행 시간메모리
569652Turkhuu밀림 점프 (APIO21_jumps)C++17
4 / 100
1109 ms64524 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int L = 18; const int inf = 1000000000; int n; vector<int> a; vector<vector<int>> lo, hi, g; bool subtask1 = true; void init(int N, vector<int> H){ n = N, a = H; g.resize(n); lo.assign(n, vector(L, -1)); hi.assign(n, vector(L, -1)); for(int i = 1; i < n; i++){ if(a[i - 1] > a[i]){ subtask1 = false; } } vector<int> idx(n); for(int i = 0; i < n; i++){ idx[--a[i]] = i; } set<int> s; for(int i = n - 1; i >= 0; i--){ auto j = s.lower_bound(idx[i]); int l = -1, r = -1; if(j != s.end()){ r = a[*j]; g[idx[i]].push_back(*j); } if(j != s.begin()){ l = a[*prev(j)]; g[idx[i]].push_back(*prev(j)); } if(l != -1 && (r == -1 || l >= r)){ lo[i][0] = r; hi[i][0] = l; } else{ lo[i][0] = l; hi[i][0] = r; } s.insert(idx[i]); } for(int j = 1; j < L; j++){ for(int i = 0; i < n; i++){ if(lo[i][j - 1] != -1){ lo[i][j] = lo[lo[i][j - 1]][j - 1]; } if(hi[i][j - 1] != -1){ hi[i][j] = hi[hi[i][j - 1]][j - 1]; } } } } int minimum_jumps(int A, int B, int C, int D){ if(subtask1){ return C - B; } if(A == B && C == D){ int H = -1; for(int i = A; i <= B; i++){ if(a[i] < a[C]){ H = max(H, a[i]); } } int G = a[C], c = 0; for(int i = L - 1; i >= 0; i--){ if(hi[H][i] != -1 && hi[H][i] <= G){ H = hi[H][i]; c += 1 << i; } } for(int i = L - 1; i >= 0; i--){ if(lo[H][i] != -1 && lo[H][i] <= G){ H = lo[H][i]; c += 1 << i; } } if(H != G){ c = -1; } return c; } queue<int> q; vector<int> d(n, inf); for(int i = A; i <= B; i++){ d[i] = 0; q.push(i); } while(!q.empty()){ int i = q.front(); q.pop(); if(C <= i && i <= D){ return d[i]; } for(int j : g[i]){ if(d[i] + 1 < d[j]){ d[j] = d[i] + 1; q.push(j); } } } 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...