제출 #613746

#제출 시각아이디문제언어결과실행 시간메모리
613746AugustinasJucas밀림 점프 (APIO21_jumps)C++14
21 / 100
1129 ms26568 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]; int lastLarger[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}); } setas.clear(); for(int i = n-1; i > -1; i--) { lastLarger[i] = -1; while(setas.size()) { if(mas[i] > setas.begin()->first) { lastLarger[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); }*/ for(int i = 0; i < n; i++) { // cout << "nuo " << i << " is kaires - " << lastLarger[i] << ", o is desines " << firstLarger[i] << endl; if(lastLarger[i] != -1) gr[i].push_back(lastLarger[i]); if(firstLarger[i] != -1) gr[i].push_back(firstLarger[i]); } } 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; } const int inf = 1e9; int dist[dydis]; void bfs(int A, int B) { queue<int> q; for(int i = 0; i < n; i++) { dist[i] = inf; } for(int i = A; i <= B; i++) { dist[i] = 0; q.push(i); } while(q.size()) { int v = q.front(); q.pop(); for(auto x : gr[v]) { // cout << "is " << v << " galiu eiti i " << x << endl; if(dist[x] > dist[v] + 1) { // cout << "nustatau dist[" << x << "] = " << dist[v] + 1 << endl; dist[x] = dist[v] + 1; q.push(x); } } } } int minimum_jumps(int A, int B, int C, int D) { bfs(A, B); int ret = inf; for(int i = C; i <= D; i++) { // cout << "dist[" << i << " ret = min(ret, dist[i]); } if(ret == inf) return -1; return ret; // 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...