Submission #1198097

#TimeUsernameProblemLanguageResultExecution timeMemory
1198097adiyerRainforest Jumps (APIO21_jumps)C++20
0 / 100
99 ms53344 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 11; int a[MAXN], l[MAXN], r[MAXN]; int d[MAXN], mn[MAXN][20]; pair < int, int > mx[MAXN][20]; bool was[MAXN]; stack < int > s; vector < int > g[MAXN]; pair < int, int > get(int l, int r){ if(l > r) return {-1, -1}; int k = __lg(r - l + 1); return max(mx[l][k], mx[r - (1 << k) + 1][k]); } int get2(int l, int r){ if(l > r) return -1; int k = __lg(r - l + 1); return min(mn[l][k], mn[r - (1 << k) + 1][k]); } void bfs(int s){ queue < int > q; q.push(s), was[s] = 1; while(!q.empty()){ int v = q.front(); q.pop(); for(int u : g[v]) if(!was[u]) was[u] = 1, d[u] = d[v] + 1, q.push(u); } } void init(int N, vector < int > H) { for(int i = 0; i < N; i++) mx[i][0] = {H[i], i}, a[i] = H[i]; for(int k = 1; k < 20; k++) for(int i = 0; i + (1 << k) - 1 < N; i++) mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]); for(int i = 0; i < N; i++){ while(!s.empty() && a[i] > a[s.top()]) s.pop(); l[i] = (s.empty() ? -1 : s.top()), s.push(i); } while(!s.empty()) s.pop(); for(int i = N - 1; i >= 0; i--){ while(!s.empty() && a[i] > a[s.top()]) s.pop(); r[i] = (s.empty() ? -1 : s.top()), s.push(i); } for(int i = 0; i < N; i++){ if(l[i] != -1) g[l[i]].push_back(i); if(r[i] != -1) g[r[i]].push_back(i); } vector < int > cur, nw; for(int i = 0; i < N; i++) cur.push_back(i); for(int rep = 0; rep < N; rep++){ for(int i : cur) if(!was[i]) nw.push_back(i); cur = nw, nw.clear(); if(cur.empty()) break; int s = cur.back(); for(int i : cur) if(a[i] > a[s]) s = i; bfs(s); } for(int i = 0; i < N; i++) mn[i][0] = d[i]; for(int k = 1; k < 20; k++) for(int i = 0; i + (1 << k) - 1 < N; i++) mn[i][k] = min(mn[i][k - 1], mn[i + (1 << (k - 1))][k - 1]); } int minimum_jumps(int A, int B, int C, int D){ if(get(B, C - 1).first > a[C]) return -1; int pos = C; return d[A] - d[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...