Submission #973680

#TimeUsernameProblemLanguageResultExecution timeMemory
973680SyriusRainforest Jumps (APIO21_jumps)C++14
44 / 100
4040 ms54228 KiB
#include <bits/stdc++.h> #include "jumps.h" using namespace std; // #define int long long #define ll long long #define ff first #define ss second #define pint pair < int , int > #define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL) typedef vector < int > vint; const int inf = 1e9 + 9; const int mxn = 2e5 + 5; const int mod = 1e9 + 7; int n; int h[mxn] , le[mxn] , ri[mxn]; int inv[mxn]; int spx[19][mxn] , spn[19][mxn]; vint v; struct node { int tl , tm , tr; int mx; node *left , *right; node (int l , int r) { tl = l , tr = r , tm = (l + r) / 2; mx = 0; left = right = NULL; } void build() { if (tl == tr) { mx = h[tl]; return; } left = new node(tl , tm); right = new node(tm+1 , tr); left -> build(); right -> build(); mx = max(left -> mx , right -> mx); } pint query(int l , int r , int x) { if (tl == tr) { if (mx > x) return {-1 , 0}; return {mx , 1}; } if (tl == l && tr == r) { if (mx < x) return {mx , 1}; pint pr = right -> query(tm+1 , r , x); if (pr.ss == 0) return pr; pint pl = left -> query(tl , tm , x); return {max(pl.ff , pr.ff) , 0}; } if (r <= tm) return left -> query(l , r , x); if (l > tm) return right -> query(l , r , x); pint pr = right -> query(tm+1 , r , x); if (pr.ss == 0) return pr; pint pl = left -> query(l , tm , x); return {max(pl.ff , pr.ff) , pl.ss}; } } *root; void init(int N , vint H) { n = N; for (int i = 0; i < n; i++) { h[i] = H[i]; inv[h[i]] = i; } root = new node(0 , n-1); root -> build(); for (int i = 0; i < n; i++) { while (v.size() > 0 && v.back() < h[i]) { ri[v.back()] = h[i]; v.pop_back(); } if (v.size() > 0) le[h[i]] = v.back(); v.push_back(h[i]); } for (int i = 0; i < n; i++) { spx[0][h[i]] = max(le[h[i]] , ri[h[i]]); spn[0][h[i]] = min(le[h[i]] , ri[h[i]]); if (spn[0][h[i]] == 0) spn[0][h[i]] = spx[0][h[i]]; } for (int j = 1; j < 19; j++) { for (int i = 0; i < n; i++) { spx[j][h[i]] = spx[j-1][spx[j-1][h[i]]]; spn[j][h[i]] = spn[j-1][spn[j-1][h[i]]]; } } } int func(int a , int d) { if (h[a] > h[d]) return -1; int dis = 0; for (int i = 18; i >= 0; i--) { if (spx[i][h[a]] > h[d] || spx[i][h[a]] == 0) continue; if (spx[i][h[a]] == h[d]) return (1 << i); int t = func(inv[spx[i][h[a]]] , d); return (t == -1) ? t : ((1<<i) + t); } for (int i = 18; i >= 0; i--) { if (spn[i][h[a]] > h[d] || spn[i][h[a]] == 0) continue; if (spn[i][h[a]] == h[d]) return (1 << i); int t = func(inv[spn[i][h[a]]] , d); return (t == -1) ? t : ((1<<i) + t); } return -1; } int minimum_jumps(int a , int b , int c , int d) { int ret = inf; for (int i = c; i <= d; i++) { int temp = (root -> query(a , b , h[i])).ff; if (temp == -1) continue; if (temp != -1) ret = min(ret , func(inv[temp] , i)); } if (ret == inf) return -1; return ret; }

Compilation message (stderr)

jumps.cpp: In function 'int func(int, int)':
jumps.cpp:106:6: warning: unused variable 'dis' [-Wunused-variable]
  106 |  int dis = 0;
      |      ^~~
#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...