BOJ 15745 Snow Boots

난이도 : Solved ac 기준 Platinum 5

출처 : USACO 2018 Feburary Contest Gold - Problem 1

 

1. 문제 설명

높이 배열 $A$ 와 쿼리 10만 개가 주어진다. 

각 쿼리는 $s_i$ 와 $d_i$ 로 구성되어 있는데, $s_i$ 는 지나갈 수 있는 최대 높이를 의미하고, $d_i$ 는 건너뛸 수 있는 최대 점프 크기를 의미한다. 즉, $d_i$ 이하의 점프로 1번부터 $N$번까지 뛰어가는데, $s_i$ 보다 높은 점을 밟지 않고 갈 수 있는지 여부를 빠르게 판정해야 한다.

 

예를 들어, 높이 배열이 $\texttt{0 3 8 5 6 9 0 0}$ 이고, $s_i = 4, d_i = 3$ 이라면 지나갈 수 없다. 1번에서 시작해서 2번까지 가더라도 3, 4, 5번 중에 밟을 수 있는 칸이 없어서 더이상 진행할 수 없기 때문이다. 하지만 $s_i = 5, d_i = 3$ 이라면 0에서 바로 5로 점프하고, 5에서 6과 9를 지나쳐서 바로 0으로 점프하면 다음 칸에 바로 목적지 도착이 가능하므로 성공으로 판정해야 한다. 

 

 

2. 풀이

문제를 바꿔서, 허용 높이가 $x$ 일 때 필요한 최소한의 점프 거리를 찾는 문제로 생각해 보자. 어차피 높이 배열에 존재하지 않는 값에 대해서는 지날 수 있는 칸의 집합이 바뀌지 않으므로, 높이 배열에 존재하는 값 10만 개에 대해서만 파악한 다음 $s_i$ 가 들어올 때마다 $s_i$ 보다 작거나 같은 최대 $x$에 대한 값을 골라 비교하면 된다.

 

이때, 높이가 낮은 순서대로 집어넣으면서 현재 set 에 있는 원소들 간의 거리 중 최댓값을 갱신한다고 생각해 보자. 예를 들어 위 예시에서는, 0이 있는 인덱스 (1, 7, 8) 을 집어넣고 이때의 최댓값인 $\abs{7 - 1} = 6$, 여기에 3이 있는 인덱스 2를 집어넣고 (1, 2, 7, 8) 에서의 거리 5... 와 같은 식으로 갱신할 수 있어야 한다. 

이 갱신 작업은 multiset에 현재의 모든 '거리' 를 저장한다고 생각하면 빠르게 처리할 수 있다. 처음에는 (8 - 1) 인 7 하나만 넣어 놓고 있다가, 중간에 7을 넣을 때 [1, 8] 구간이 깨지고 [1, 7] 과 [7, 8] 로 쪼개지는 것이므로 multiset에서 깨지는 구간을 하나 빼고 생기는 구간을 2개 넣는 식으로 진행하면, 최대 20만 개의 원소가 들어가 있게 된다. $\texttt{multiset.rbegin()}$으로 빠르게 최댓값을 챙길 수 있으므로 전체 시간 복잡도 $\mathcal{O}(N \log N + B \log N)$ 에 해결할 수 있다.

 

 

3. 코드

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

int n, b;
map <int, vector<int>> mp;
map <int, int> ansmp;
set <int> st;
multiset<int> alldist;
void dins(int xx)
{
    if (xx == 0) return;
    else alldist.insert(xx);
}
void ers(int xx)
{
    if (alldist.lower_bound(xx) == alldist.end())
        return;
    alldist.erase(alldist.lower_bound(xx));
}
void stinsert(int ins)
{
    if (st.empty())
    {
        st.insert(ins);
        ers(n-1);
        dins(n-ins);
        dins(ins-1);
        return;
    }
    if (ins < *st.begin())
    {
        ers(*st.begin()-1);
        dins(*st.begin()-ins);
        dins(ins-1);
        st.insert(ins);
        return;
    }
    if (ins > *st.rbegin())
    {
        ers(n-*st.rbegin());
        dins(ins-*st.rbegin());
        dins(n-ins);
        st.insert(ins);
        return;
    }
    auto tt = st.lower_bound(ins);
    tt--;
    int u = *(tt);
    int v = *st.upper_bound(ins);
    ers(v-u);
    dins(v-ins);
    dins(ins-u);
    st.insert(ins);
    return;
}
int main()
{
    usecppio
    cin >> n >> b;
    for (int i = 1; i<= n; i++)
    {
        int x; cin >> x;
        mp[x].push_back(i);
    }
    int ans = n-1;
    for (auto it:mp)
    {
        int x = it.first;
        for (auto itt:it.second)
            stinsert(itt);
        if (alldist.empty()) ans = 0;
        else
            ans = *alldist.rbegin();
        ansmp[x] = ans;
    }
    ansmp[-1] = INT_MAX;
    while(b--)
    {
        int f, d;
        cin >> f >> d;
        cout << (((*(--ansmp.upper_bound(f))).second <= d)?1:0) << '\n';
    }
}