제출 #887759

#제출 시각아이디문제언어결과실행 시간메모리
887759Iliya_밀림 점프 (APIO21_jumps)C++17
37 / 100
4011 ms14556 KiB
//IN THE NAME OF GOD #include<bits/stdc++.h> #pragma GCC optimize("O2,unroll-loops") #define endl '\n' #define F first #define S second #define pii pair<int,int> #define all(x) x.begin(),x.end() #define pb push_back #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define file_io freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout); using namespace std; typedef long long ll; typedef long double dll; const int N = 2e5+7, inf = 1e9; vector<int> g[N],vec; int dist[N], n; bool sub1 = false; queue<int> q; #include "jumps.h" void init(int _n, vector<int> h){ n = _n; sub1 = true; for(int i=0; i<n; i++) if (h[i] != i+1) sub1 = false; vec.pb(0); for(int i=0; i<n; i++){ while(vec.size() && h[vec.back()] < h[i]) vec.pop_back(); if (vec.size()) g[i].pb(vec.back()); vec.pb(i); } vec.clear(); vec.pb(n-1); for(int i=n-2; i>=0; i--){ while(vec.size() && h[vec.back()] < h[i]) vec.pop_back(); if (vec.size()) g[i].pb(vec.back()); vec.pb(i); } } int minimum_jumps(int a, int b, int c, int d){ if (sub1) return c-b; fill(dist,dist+n,inf); for(int i=a; i<=b; i++){ dist[i] = 0; q.push(i); } while(q.size()){ int v = q.front(); q.pop(); for(int u : g[v]){ if (dist[u] > dist[v] + 1){ dist[u] = dist[v] + 1; q.push(u); } } } int mn = inf; for(int i=c; i<=d; i++) mn = min(mn,dist[i]); return (mn == inf ? -1 : mn); } /* int32_t main(){ fast_io; vector<int> tmp = {3, 2, 1, 6, 4, 5, 7}; init(7, tmp); for(int i=0; i<n; i++){ cout << "Hello " << i << endl; for(int u : g[i]) cout << u << " "; cout << endl; } cout << minimum_jumps(4, 4, 6, 6) << endl; return 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...