| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1118714 | Zero_OP | 밀림 점프 (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e3 + 5;
const int inf = 1e9;
int N, H[MAX];
vector<int> adj[MAX];
int rmq[11][11][MAX][MAX];
vector<int> bfs(int s){
vector<int> d(N, inf);
queue<int> q;
q.push(s);
d[s] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(auto v : adj[u]){
if(d[v] == inf){
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d;
}
void init(int _N, int _H[]){
N = _N;
copy(_H, _H + N, H);
stack<int> st;
for(int i = 0; i < N; ++i){
while(!st.empty() && H[st.top()] <= H[i]) st.pop();
if(!st.empty()) adj[i].emplace_back(st.top());
st.push(i);
}
stack<int>().swap(st);
for(int i = N - 1; i >= 0; --i){
while(!st.empty() && H[st.top()] <= H[i]) st.pop();
if(!st.empty()) adj[i].emplace_back(st.top());
st.push(i);
}
for(int i = 0; i < N; ++i){
vector<int> d = bfs(i);
for(int j = 0; j < N; ++j){
rmq[0][0][i][j] = d[j];
}
}
for(int u = 0; (1 << u) <= N; ++u){
for(int i = 0; i + (1 << u) <= N; ++i){
for(int v = 0; (1 << v) <= N; ++v){
for(int j = 0; j + (1 << v) <= N; ++j){
if(u == 0){
if(v > 0){
rmq[u][v][i][j] = min(rmq[u][v - 1][i][j], rmq[u][v - 1][i][j + (1 << (v - 1))]);
}
} else{
rmq[u][v][i][j] = min(rmq[u - 1][v][i][j], rmq[u - 1][v][i + (1 << (u - 1))][j]);
}
}
}
}
}
}
int minimum_jumps(int a, int b, int c, int d){
int u = 31 - __builtin_clz(b - a + 1);
int v = 31 - __builtin_clz(d - c + 1);
int cur = min({rmq[u][v][a][c], rmq[u][v][a][d - (1 << v) + 1],
rmq[u][v][b - (1 << u) + 1][c], rmq[u][v][b - (1 << u) + 1][d - (1 << v) + 1]});
return (cur == inf ? -1 : cur);
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int N, Q;
cin >> N >> Q;
int H[N];
for(int i = 0; i < N; ++i){
cin >> H[i];
}
init(N, H);
for(int i = 0; i < Q; ++i){
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << minimum_jumps(a, b, c, d) << '\n';
}
return 0;
}
#endif //LOCAL