BOJ)15745 Snow Boots

문제: icpc.me/15745

1~N 영역에 쌓인 눈의 높이가 주어진다.

이제 B개의 신발에 대한 쿼리가 들어오는데 각 쿼리는 Si와 Di를 가진다. 

Si는 해당 신발을 신고 걸을 수 있는 최대 눈의 높이이고, Di는 한번에 최대로 걸을 수 있는 거리이다.

i번 째 신발을 신었을 때 1에서 부터 N까지 갈 수 있는 지 여부를 매 쿼리마다 출력해주면 되는 문제이다.

풀이법은 여러가지가 있는것 같지만 내가 푼 풀이는 오프라인 쿼리 풀이이다.

우선 쿼리를 Si기준으로 역순으로 정렬을 해준 뒤 순서대로 봐준다.

쿼리를 역순으로 본다면, 쿼리를 보면서 점점 못넘는 영역이 늘어날 것이다. 

현재 쿼리를 처리할 때 넘을 수 있는 기준은 현재 못넘는 영역중에서 가장 긴 영역이 되므로

역순으로 쿼리를 처리하면서, 못넘는 영역을 계속 처리해주면 된다. 못넘는 영역의 크기는 union find를 이용하면 쉽게 처리해줄 수 있다.

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int n,b,a[100010],m[100010],par[100010],sz[100010],r[100010],currmaxsize,finish;
map<int,vector<int>> mp;
vector<pair<pair<int,int>,int>> qry;
int find(int h){
    return h==par[h]?h:par[h]=find(par[h]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    par[x]=y;
    sz[y]+=sz[x];
}
int main(){
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)par[i]=i,sz[i]=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mp[a[i]].push_back(i);
    }
    for(int i=0;i<b;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        qry.push_back({{x,y},i});
    }
    sort(qry.rbegin(),qry.rend());
    auto it=mp.end();
    it--;
    currmaxsize=0;
    for(int i=0;i<b;i++){
        while(!finish){
            if(it->first<=qry[i].first.first)break;
            for(auto idx:it->second){
                if(idx!=1&&m[idx-1])
                    merge(idx-1,idx);
                if(idx!=n&&m[idx+1])
                    merge(idx+1,idx);
                m[idx]=1;
                currmaxsize=max(currmaxsize,sz[find(idx)]);
            }
            if(it==mp.begin())finish=1;
            it--;
        }
        if(qry[i].first.second>currmaxsize)
            r[qry[i].second]=1;
    }
    for(int i=0;i<b;i++)printf("%d\n",r[i]);
    return 0;
}