Submission #917589

#TimeUsernameProblemLanguageResultExecution timeMemory
917589hariaakas646Rainforest Jumps (APIO21_jumps)C++14
33 / 100
4069 ms15436 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; #define scd(t) scanf("%d", &t) #define sclld(t) scanf("%lld", &t) #define forr(i, l, r) for(int i=l; i<r; i++) #define frange(i, l) forr(i, 0, l) #define pb push_back #define mp make_pair #define f first #define s second #define all(x) x.begin(), x.end() typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pii> vii; typedef long long lli; typedef vector<vi> vvi; typedef vector<lli> vll; typedef vector<bool> vb; typedef set<int> seti; typedef multiset<int> mseti; vvi graph; int n; void init(int N, std::vector<int> h) { n = N; graph = vvi(n); deque<int> dq; frange(i, n) { while(dq.size() && h[i] >= h[dq.back()]) dq.pop_back(); if(dq.size()) graph[i].pb(dq.back()); dq.pb(i); } dq = {}; for(int i=n-1; i>=0; i--) { while(dq.size() && h[i] >= h[dq.back()]) dq.pop_back(); if(dq.size()) graph[i].pb(dq.back()); dq.pb(i); } } int minimum_jumps(int A, int B, int C, int D) { queue<pii> q; forr(i, A, B+1) q.push(mp(i, 0)); vb vis(n); while(q.size()) { auto p = q.front(); q.pop(); if(C <= p.f && p.f <= D) return p.s; if(vis[p.f]) continue; vis[p.f] = true; for(auto e : graph[p.f]) { q.push(mp(e, p.s+1)); } } 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...