| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 998226 | thelegendary08 | 밀림 점프 (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0;i<n;i++)
#define pb push_back
#define ll long long int
#define vi vector<ll>
using namespace std;
const int mxn = 200005;
int v[mxn];
int n;
vi adj[mxn];
const int mxn2 = 2005;
int dist[mxn2][mxn2];
int tree[mxn2][mxn2 * 4];
void upd(int dex, int pos, int num){
pos += n;
tree[dex][pos] = num;
for(pos/=2; pos >= 1; pos/=2){
tree[dex][pos] = min(tree[dex][pos * 2], tree[dex][pos * 2 + 1]);
}
}
int quer(int dex, int l, int r){
l += n; r+=n;
int ret = 1e9;
while(l <= r){
if(l % 2 == 1){
ret = min(ret, tree[dex][l++]);
}
if(r % 2 == 0){
ret = min(ret, tree[dex][r--]);
}
l/=2;
r/=2;
}
return ret;
}
void init(int N, std::vector<int> H) {
n = N;
f0r(i,N)v[i] = H[i];
int dex[n+1];
f0r(i,n){
dex[v[i]] = i;
}
stack<int>s;
f0r(i, n){
while(!s.empty() && v[s.top()] < v[i]){
s.pop();
}
if(!s.empty())adj[i].pb(s.top());
s.push(i);
}
for(int i = n-1;i>=0;i--){
while(!s.empty() && v[s.top()] < v[i]){
s.pop();
}
if(!s.empty())adj[i].pb(s.top());
s.push(i);
}
if(n <= 2000){
f0r(i, n)f0r(j,n)dist[i][j] = 1e9;
f0r(i,n){
queue<int>q;
dist[i][i] = 0;
vector<bool>vis(n, false);
vis[i] = 1;
q.push(i);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(vis[u])continue;
vis[u] = 1;
q.push(u);
dist[i][u] = min(dist[i][cur] + 1, dist[i][u]);
}
}
}
f0r(i, n){
f0r(j, n){
upd(i, j, dist[i][j]);
}
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(n > 2000){
vector<bool>vis(n, 0);
vi dist(n);
queue<int>q;
for(int i = A;i<=B;i++){
dist[i] = 0;
vis[i] = 1;
q.push(i);
}
bool stop = 0;
int ans = 0;
while(!(stop || q.empty())){
int c = q.front();
q.pop();
for(auto u : adj[c]){
if(vis[u])continue;
vis[u] = 1;
dist[u] = dist[c] + 1;
q.push(u);
if(u >= C && u <= D){
ans = u;
stop = 1;
}
}
}
if(!stop)return -1;
else return dist[ans];
}
else{
int ans = 1e9;
for(int i = A; i<=B;i++){
ans = min(ans, quer(i, C, D));
}
if(ans == 1e9)return -1;
else return ans;
}
}
int main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int A, B, C, D;
assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}