Submission #998276

#TimeUsernameProblemLanguageResultExecution timeMemory
998276thelegendary08Rainforest Jumps (APIO21_jumps)C++14
0 / 100
4094 ms73880 KiB
#include "jumps.h" #include<bits/stdc++.h> #define f0r(i,n) for(int i = 0;i<n;i++) #define pb push_back #define ll long long int #define vi vector<ll> using namespace std; const int mxn = 200005; int v[mxn]; int n; vi adj[mxn]; vector<vi> l(18, vi(mxn, 1e9)); vector<vi> h(18, vi(mxn, 1e9)); const int mxn2 = 2005; int dist[mxn2][mxn2]; int tree[mxn2][mxn2 * 4]; void upd(int dex, int pos, int num){ pos += n; tree[dex][pos] = num; for(pos/=2; pos >= 1; pos/=2){ tree[dex][pos] = min(tree[dex][pos * 2], tree[dex][pos * 2 + 1]); } } int quer(int dex, int l, int r){ l += n; r+=n; int ret = 1e9; while(l <= r){ if(l % 2 == 1){ ret = min(ret, tree[dex][l++]); } if(r % 2 == 0){ ret = min(ret, tree[dex][r--]); } l/=2; r/=2; } return ret; } void init(int N, std::vector<int> H) { n = N; f0r(i,N)v[i] = H[i]; int dex[n+1]; f0r(i,n){ dex[v[i]] = i; } stack<int>s; f0r(i, n){ while(!s.empty() && v[s.top()] < v[i]){ s.pop(); } if(!s.empty())adj[i].pb(s.top()); s.push(i); } s = stack<int>(); for(int i = n-1;i>=0;i--){ while(!s.empty() && v[s.top()] < v[i]){ s.pop(); } if(!s.empty())adj[i].pb(s.top()); s.push(i); } f0r(i,n){ if(adj[i].size() == 1)l[0][i] = adj[i][0]; else if(adj[i].size() == 2){ l[0][i] = min(adj[i][0], adj[i][1]); h[0][i] = max(adj[i][0], adj[i][1]); } } for(int i = 1;i<18;i++){ f0r(j, n){ if(l[i-1][j] != 1e9)l[i][j] = l[i-1][l[i-1][j]]; if(h[i-1][j] != 1e9)h[i][j] = h[i-1][h[i-1][j]]; } } f0r(i, 18){ f0r(j, n){ //cout<<l[i][j]<<' '; } //cout<<'\n'; } if(n <= 2000){ f0r(i, n)f0r(j,n)dist[i][j] = 1e9; f0r(i,n){ queue<int>q; dist[i][i] = 0; vector<bool>vis(n, false); vis[i] = 1; q.push(i); while(!q.empty()){ int cur = q.front(); q.pop(); for(auto u : adj[cur]){ if(vis[u])continue; vis[u] = 1; q.push(u); dist[i][u] = min(dist[i][cur] + 1, dist[i][u]); } } } f0r(i, n){ f0r(j, n){ upd(i, j, dist[i][j]); } } } } int minimum_jumps(int A, int B, int C, int D) { if(A == B && C == D){ int cur = A; int t = D; int ans = 0; for(int i = 17;i>=0;i--){ if(h[i][cur] < n && v[h[i][cur]] <= v[t]){ cur = h[i][cur]; ans += (1 << i); } } for(int i = 17; i>=0; i--){ if(l[i][cur] < n && v[l[i][cur]] <= v[t]){ cur = l[i][cur]; ans += (1 << i); } } if(cur != t)return -1; else return ans; } else if(n > 2000){ vector<bool>vis(n, 0); vi dist(n); queue<int>q; for(int i = A;i<=B;i++){ dist[i] = 0; vis[i] = 1; q.push(i); } bool stop = 0; int ans = 0; while(!(stop || q.empty())){ int c = q.front(); q.pop(); for(auto u : adj[c]){ if(vis[u])continue; vis[u] = 1; dist[u] = dist[c] + 1; q.push(u); if(u >= C && u <= D){ ans = u; stop = 1; } } } if(!stop)return -1; else return dist[ans]; } else{ int ans = 1e9; for(int i = A; i<=B;i++){ ans = min(ans, quer(i, C, D)); } if(ans == 1e9)return -1; else return ans; } }

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:44:6: warning: variable 'dex' set but not used [-Wunused-but-set-variable]
   44 |  int dex[n+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...