스카이라인

서브태스크 1에서는 각 건물마다 다른 모든 건물을 직접 검사한다. 시간은 $O(\sum N^2)$이고 $N\leq100$, $\sum N\leq1000$이므로 충분하다.

전체 풀이에서는 $L_X=\max(A_1,\cdots,A_{X-1})$, 을 사용한다. 비어 있는 왼쪽은 , 오른쪽은 로 둔다. 왼쪽 조건은 와 동치이고, 오른쪽 조건은 와 동치이다. 따라서 두 비교를 모두 만족하는 위치만 세면 정확하다. 오른쪽 최솟값은 뒤에서 미리 계산하고 왼쪽 최댓값은 앞에서 갱신한다. 같은 높이도 허용되므로 비엄격 부등호를 사용한다. 시간은 , 추가 공간은 이다. 모든 저장값은 이하이고 답은 이하이다.

Solution written by GPT6.1