현영

2289.cpp

#include <stdio.h>

int arr[80000];
int building[80000];
int index[80000];
int result[80000];

int main()
{
    int n;
    scanf("%d", &n);
    
    for( int i = 0 ; i < n ; i ++ ){
        scanf("%d", &arr[i]);
    }

    int saved_count = -1;
    for( int i = 0 ; i < n ; i ++ ){
        while( saved_count >= 0 ){
            if( building[ saved_count ] < arr[i] ){      // i번째 건물이 저장해둔 높이보다 크면, 저장한 높이의 건물은 막혀서 더 이상 다른 건물을 볼 수 없게 된다. 이때 저장한 건물은 (i - 자기 자신의 번호 - 1) 개 만큼을 볼 수 있다는 사실이 자명하다.
                result[ index[saved_count] ] = i - index[saved_count] - 1;
                saved_count--;
                // building, index 배열을 굳이 지우지 않아도 saved_count 변수가 줄어들면 나중에 알아서 덮어씀
            }
        }
        building[++saved_count] = arr[i];
        index[saved_count] = i;        
    }
    // 남은 건물들은 그냥 오른쪽에 있는 모든 건물들을 볼 수 있으므로 위치를 기준으로 갯수를 세준다
    while( saved_count >= 0 ){
        result[ index[saved_count] ] = n - index[saved_count] - 1;
        saved_count --;
    }

    int dap = 0;
    for( int i = 0 ; i < n ; i ++ ){
        dap += result[i];
    }
    printf("%d\n", dap);
    for( int i = 0 ; i < n ; i ++ ){
        printf("%d\n", result[i]);
    }
}