Submission #917933

#TimeUsernameProblemLanguageResultExecution timeMemory
917933hariaakas646Rainforest Jumps (APIO21_jumps)C++14
23 / 100
755 ms43656 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; vvi lifti, lifta; vi hgt; int lift(int x, int h) { int c = 0; for(int i=19; i>=0; i--) { int xt = lifta[i][x]; if(hgt[xt] < h) { x = xt; c+=(1<<i); } } if(hgt[lifta[0][x]] == h) return c + 1; for(int i=19; i>=0; i--) { int xt = lifti[i][x]; if(hgt[xt] < h) { x = xt; c += (1<<i); } } if(hgt[lifti[0][x]] == h) return c + 1; else return -1; } void init(int N, std::vector<int> h) { n = N; graph = vvi(n); hgt = h; deque<int> dq; vii mi(n, mp(2e9, -1)), ma(n, mp(-1, -1)); frange(i, n) { while(dq.size() && h[i] >= h[dq.back()]) dq.pop_back(); if(dq.size()) { mi[i] = mp(h[dq.back()], dq.back()); ma[i] = mp(h[dq.back()], 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()) { pii p = mp(h[dq.back()], dq.back()); if(p > ma[i]) ma[i] = p; if(p < mi[i]) mi[i] = p; } dq.pb(i); } lifti = lifta = vvi(20, vi(n)); frange(i, n) { if(mi[i].s != -1) lifti[0][i] = mi[i].s; else lifti[0][i] = i; if(ma[i].s != -1) lifta[0][i] = ma[i].s; else lifta[0][i] = i; } forr(i, 1, 20) { frange(j, n) { lifti[i][j] = lifti[i-1][lifti[i-1][j]]; lifta[i][j] = lifta[i-1][lifta[i-1][j]]; } } } 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)); // } // } // if(d < a) // return -1; // else return max(0, c - b); return lift(A, hgt[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...