Submission #1236316

#TimeUsernameProblemLanguageResultExecution timeMemory
1236316AMel0nRainforest Jumps (APIO21_jumps)C++20
33 / 100
4089 ms20160 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,N) for(ll i = 0; i < N; i++) #define all(x) (x).begin(), (x).end() #define F first #define S second #include "jumps.h" int N; vector<int> H; vector<vector<int>> g; vector<int> tree; void update(int v, int p, int tl = 0, int tr = N-1, int i = 1) { if (tl == tr) {tree[i] = v; return ;} int tm = (tl + tr) / 2; if (p <= tm) update(v, p, tl, tm, i * 2); else update(v, p, tm + 1, tr, i * 2 + 1); tree[i] = max(tree[i * 2], tree[i * 2 + 1]); } int query(int l, int r, int tl = 0, int tr = N-1, int i = 1) { if (l > r) return -1e9; if (tl == l && tr == r) return tree[i]; int tm = (tl + tr) / 2; return max(query(l, min(tm, r), tl, tm, i * 2), query(max(tm + 1, l), r, tm + 1, tr, i * 2 + 1)); } void init(int N, std::vector<int> H) { ::N = N; ::H = H; g.resize(N); tree.resize(N*4); FOR(i, N) update(H[i], i); FOR(i, N) { int l = i+1, r = N+1; while(l < r - 1) { int m = (l + r - 1) / 2; if (query(i+1, m) <= H[i]) { l = m + 1; } else { r = m + 1; } } if (l != N) g[i].push_back(l); l = -1, r = i; while(l < r - 1) { int m = (l + r) / 2; if (query(m, i-1) <= H[i]) { r = m; } else { l = m; } } if (l != -1) g[i].push_back(l); } } int minimum_jumps(int A, int B, int C, int D) { priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq; vector<int> vis(N, 1e9); for(int i = A; i <= B; i++) { pq.push({0, i}); vis[i] = 0; } while(pq.size()) { int d = pq.top().F; int u = pq.top().S; pq.pop(); if (vis[u] != d) continue; for(int v: g[u]) { if (vis[v] > d+1) { pq.push({d+1, v}); vis[v] = d+1; } } } int res = 1e9; for(int i = C; i <= D; i++) { res = min(res, vis[i]); } return (res == 1e9) ? -1 : res; }
#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...