| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 569365 | BadPenalty | 밀림 점프 (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 1e6,mod = 1e9+7;
vector<int>A;
vector<int>adj[N];
int n,dst[N];
bool vstd[N];
void init(int N, std::vector<int> H)
{
n = N;
A = H;
set<int>s;
s.insert(A[0]);
for(int i = 1;i<n;i++)
{
while(!s.empty()&&*s.begin()<A[i])
s.erase(s.begin());
if(!s.empty())
adj[A[i]].pb(*s.begin());
s.insert(A[i]);
}
s.clear();
s.insert(A[n-1]);
for(int i = n-2;i>=0;i--)
{
while(!s.empty()&&*s.begin()<A[i])
s.erase(s.begin());
if(!s.empty())
adj[A[i]].pb(*s.begin());
s.insert(A[i]);
}
return;
}
int minimum_jumps(int a, int B, int C, int D)
{
for(int i = 0;i<n;i++)
vstd[i] = 0,dst[A[i]] = 1e9;
queue<int>q;
for(int i = a;i<=B;i++)
{
q.push(A[i]);
dst[A[i]] = 0;
}
while(!q.empty())
{
int nd = q.front();
q.pop();
if(vstd[nd])continue;
vstd[nd] = 1;
for(auto u:adj[nd])
{
if(dst[u]>dst[nd]+1)
{
dst[u] = dst[nd]+1;
q.push(u);
}
}
}
int ans = 1e9;
for(int i = C;i<=D;i++)
{
ans = min(ans,dst[A[i]]);
}
if(ans!=1e9)
return ans;
return -1;
}
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;
}