제출 #975370

#제출 시각아이디문제언어결과실행 시간메모리
975370Syrius밀림 점프 (APIO21_jumps)C++14
0 / 100
197 ms49184 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 , mn; node *left , *right; node (int l , int r) { tl = l , tr = r , tm = (l + r) / 2; mx = 0; mn = inf; left = right = NULL; } void build() { if (tl == tr) { mx = mn = h[tl]; return; } left = new node(tl , tm); right = new node(tm+1 , tr); left -> build(); right -> build(); mx = max(left -> mx , right -> mx); mn = min(left -> mn , right -> mn); } 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}; } pint queryy(int l , int r , int x) { if (tl == tr) { if (mn < x) return {-1 , 0}; return {mn , 1}; } if (tl == l && tr == r) { if (mn > x) return {mn , 1}; pint pr = right -> queryy(tm+1 , r , x); if (pr.ss == 0) return pr; pint pl = left -> queryy(tl , tm , x); return {min(pl.ff , pr.ff) , 0}; } if (r <= tm) return left -> queryy(l , r , x); if (l > tm) return right -> queryy(l , r , x); pint pr = right -> queryy(tm+1 , r , x); if (pr.ss == 0) return pr; pint pl = left -> queryy(l , tm , x); return {min(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 ans = inf; int hmax = root -> query(a , c-1 , inf).ff; int h2 = root -> query(c , d , inf).ff; int h1 = root -> query(a , b , h2).ff; if (h1 == -1) return -1; int hbef = -1; if (a > 0) hbef = root -> queryy(0 , a-1 , hmax).ff; if (hbef != -1 && hbef < h2) ans = min(ans , 1 + func(a , inv[hbef])); int hmid = -1; if (b + 1 != c) hmid = root -> query(b+1 , c-1 , inf).ff; else return 1; if (hmid > h2) return -1; if (h1 > hmid) return 1; if (hmid != -1) ans = min(ans , 1 + func(a , inv[hmid])); return (ans == inf) ? -1 : ans; }

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int func(int, int)':
jumps.cpp:129:6: warning: unused variable 'dis' [-Wunused-variable]
  129 |  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...