D. Mike and Feet

Disjoint Set Union(dsu)

출처: Codeforces D. Mike and Feet

sol)
현재 이 값이 양 옆으로 얼마나 갈 수 있나? 를 응용
오름 차순 순으로 정렬후 하나씩 집합으로 만들어 나가고
어느 정도 길이로 갈 수 있는지 조사를 한다.
isMerge = -1이면 아직 집합이 아니며
isMerge != -1이면 길이를 알 수 있다.

주석 친 부분은 필요가 없다.
맨 아래 답을 출력하기 전에 이전의 값과 비교 후 max값을
유지하기 때문에..




[-] Collapse

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

vector<pair<int, int> > h;
int ori[200002];
int isMerge[200002];
int ans[200002];
int par[200002];

int find(int idx){
    if (par[idx] == idx) return idx;
    else return par[idx] = find(par[idx]);
}

void merge(int l, int r){
    l = find(l); r = find(r);
    par[r] = l;
}

int main(){
    //freopen("input.txt", "r", stdin);
    for (int i = 0; i < 200002; i++){
        isMerge[i] = -1;
        par[i] = i;
    }

    int n; scanf("%d", &n);
    ori[0] = ori[n+1] = 0;
    for (int i = 1; i <= n; i++){
        scanf("%d", &ori[i]);
        h.push_back(make_pair(ori[i], i));
    }

    sort(h.rbegin(), h.rend());

    for (int i = 0; i < n; i++){
        int height = h[i].first;
        int idx = h[i].second;
        int len = 1;
        if (isMerge[idx - 1] != -1 && ori[idx - 1] >= height){
            len += isMerge[find(idx - 1)];
            merge(idx, idx - 1);
            //ans[len] = max(ans[len], height);
        }
        if (isMerge[idx + 1] != -1 && ori[idx + 1] >= height){
            len += isMerge[find(idx + 1)];
            merge(idx, idx + 1);
            //ans[len] = max(ans[len], height);
        }
        ans[len] = max(ans[len], height);
        isMerge[idx] = len;
    }
    for (int i = n - 1; i >= 1; i--) ans[i] = max(ans[i], ans[i + 1]);
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}