6029 : 빌딩 조망권
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 2
•통과: 1
•만든사람: suakii
문제 설명
$N$개의 빌딩이 한 줄로 서 있고, 각 빌딩의 높이가 주어집니다.
각 빌딩에서 왼쪽과 오른쪽을 수평으로 바라보았을 때, 자신보다 높이가 낮은 빌딩들 중 막히지 않고 관측할 수 있는 빌딩들의 개수의 합을 구하십시오.
수평선 상에서 자신보다 같거나 큰 빌딩을 만나면 그 너머의 빌딩들은 더 이상 볼 수 없습니다.
각 빌딩에서 왼쪽과 오른쪽을 수평으로 바라보았을 때, 자신보다 높이가 낮은 빌딩들 중 막히지 않고 관측할 수 있는 빌딩들의 개수의 합을 구하십시오.
수평선 상에서 자신보다 같거나 큰 빌딩을 만나면 그 너머의 빌딩들은 더 이상 볼 수 없습니다.
입력 설명
첫째 줄에 빌딩의 수 $N$이 주어집니다. ($1 \le N \le 100,000$)
둘째 줄에 각 빌딩의 높이가 공백으로 구분되어 주어집니다.
둘째 줄에 각 빌딩의 높이가 공백으로 구분되어 주어집니다.
출력 설명
각 빌딩에서 볼 수 있는 빌딩 수(왼쪽 + 오른쪽 합산)를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
3 7 2 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0 3 0 1도움
단조 스택을 사용하여 각 빌딩의 왼쪽 및 오른쪽에서 처음으로 자기 자신보다 같거나 큰 빌딩이 등장하는 인덱스 $L, R$을 찾은 뒤, 거리의 합을 구합니다.