티스토리 뷰

알고리즘 관련/BOJ

BOJ)15745 Snow Boots

JASON 자손9319 2018. 7. 3. 12:52

문제: icpc.me/15745


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


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


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


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


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14288 내리 갈굼4  (1) 2018.07.07
BOJ)14400 편의점2  (0) 2018.07.05
BOJ)15745 Snow Boots  (0) 2018.07.03
BOJ)13274 수열  (0) 2018.07.02
BOJ)15589 Lifeguards (Silver)  (0) 2018.06.26
BOJ)14965 Lozinke  (0) 2018.06.26
댓글
댓글쓰기 폼