제출 #613722

#제출 시각아이디문제언어결과실행 시간메모리
613722AugustinasJucas밀림 점프 (APIO21_jumps)C++14
0 / 100
260 ms25564 KiB
#include "jumps.h" #include <vector> #include <bits/stdc++.h> using namespace std; int n; vector<int> mas; const int dydis = 1e5 + 10; const int dd = 20; int mx[dydis][dd]; int lg2[dydis]; void build() { lg2[1] = 0; for(int i = 2; i < dydis; i++) lg2[i] = lg2[i/2] + 1; for(int i = 0; i < n; i++) { mx[i][0] = mas[i]; } for(int j = 1; j < dd; j++) { for(int i = 0; i < n; i++) { int r = i + (1 << (j-1)); r = min(r, n-1); mx[i][j] = max(mx[i][j-1], mx[r][j-1]); } } } vector<int> gr[dydis]; int h[dydis]; void dfs(int v) { for(auto x : gr[v]) { h[x] = h[v] + 1; dfs(x); } } int getMx(int a, int b) { int pw = lg2[b - a + 1]; // cout << a << "; " << b << " issiskaido i intervala [" << a << "; " << a + (1 << pw) - 1 << "] ir intervala [" << b - (1 << pw) + 1 << "; " << b << "]\n"; int ind = b - (1 << pw) + 1; return max(mx[a][pw], mx[ind][pw]); } int firstLarger[dydis]; void init(int N, vector<int> H) { n = N ; mas = H; build(); set<pair<int, int> > setas; for(int i = 0; i < n; i++) { firstLarger[i] = -1; while(setas.size()) { if(mas[i] > setas.begin()->first) { firstLarger[setas.begin()->second] = i; setas.erase(*setas.begin()); }else break; } setas.insert({mas[i], i}); } vector<int> roots; for(int i = 0; i < n; i++) { if(firstLarger[i] == -1) { roots.push_back(i); }else { gr[firstLarger[i]].push_back(i); } } for(auto x : roots) { h[x] = 0; dfs(x); } } bool arGalima(int a, int b) { /// ar galima is a i b? if(mas[a] >= mas[b]) return false; if(a == b-1) return true; if(getMx(a+1, b-1) < b) return true; return false; } int minimum_jumps(int A, int B, int C, int D) { // cout << "maximumas tarp " << A << " ir " << C << " yra " << getMx(A, C) << endl; if(arGalima(A, C) == false) return -1; return h[A] - h[C]; }
#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...