제출 #743365

#제출 시각아이디문제언어결과실행 시간메모리
743365saayan007밀림 점프 (APIO21_jumps)C++17
21 / 100
526 ms1048576 KiB
#include "bits/stdc++.h" using namespace std; #define fr first #define sc second #define eb emplace_back const char nl = '\n'; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x) #else #define dbg(x...) #endif vector<int> L, R; vector<vector<int>> dist; int n; void init(int N, std::vector<int> H) { n = N; L.resize(n); stack<int> st; for(int i = 0; i < n; ++i) { while(!st.empty() && H[st.top()] < H[i]) st.pop(); L[i] = (st.empty() ? -1 : st.top()); st.push(i); } while(!st.empty()) st.pop(); R.resize(n); for(int i = n - 1; i >= 0; --i) { while(!st.empty() && H[st.top()] < H[i]) st.pop(); R[i] = (st.empty() ? -1 : st.top()); st.push(i); } /* for(int i = 0; i < N; ++i) { */ /* cout << i << " : " << L[i] << ' ' << R[i] << nl; */ /* } */ dist = vector<vector<int>>(n, vector<int>(n, -1)); for(int x = 0; x < n; ++x) { dist[x][x] = 0; queue<int> q; q.emplace(x); while(!q.empty()) { int y = q.front(); q.pop(); if(L[y] != -1 && dist[x][L[y]] == -1) { dist[x][L[y]] = dist[x][y] + 1; q.emplace(L[y]); } if(R[y] != -1 && dist[x][R[y]] == -1) { dist[x][R[y]] = dist[x][y] + 1; q.emplace(R[y]); } } for(int y = 0; y < n; ++y) { /* cout << dist[x][y] << ' '; */ if(dist[x][y] == -1) dist[x][y] = 10*n; } /* cout << nl; */ } } int minimum_jumps(int A, int B, int C, int D) { int opt = 10*n; for(int x = A; x <= B; ++x) { for(int y = C; y <= D; ++y) { opt = min(opt, dist[x][y]); } /* for(int j = 0; j < n; ++j) dist[j] = -1; */ /* dist[x] = 0; */ /* queue<int> q; */ /* q.emplace(x); */ /* while(!q.empty()) { */ /* int y = q.front(); q.pop(); */ /* if(C <= y && y <= D) opt = min(opt, dist[y]); */ /* if(L[y] != -1 && dist[L[y]] == -1) { */ /* dist[L[y]] = dist[y] + 1; */ /* q.emplace(L[y]); */ /* } */ /* if(R[y] != -1 && dist[R[y]] == -1) { */ /* dist[R[y]] = dist[y] + 1; */ /* q.emplace(R[y]); */ /* } */ /* } */ } return opt > n ? -1 : opt; }
#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...