시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 302 | 71 | 49 | 28.994% |
상근이는 새 화면 보호기를 설치했다. 컴퓨터를 5분동안 사용하지 않으면 화면 보호기가 실행된다. 이 화면 보호기는 수족관 그림과 움직이는 물고기를 보여준다. 화면 보호기 설정 화면에서는 바닥의 모양과 수면의 높이를 설정할 수 있다.
수족관은 너비가 N-1인 2차원 평면으로 나타낼 수 있다. 이때, N은 양의 정수이다. 수족관의 가장 왼쪽 x좌표는 0이고, 가장 오른쪽 x좌표는 N-1이다. 각 정수 x좌표 i는 바닥의 높이 Hi를 갖는다. 이 높이는 설정에서 바꿀 수 있다. 바닥은 인접한 두 x좌표 i와 i+1를 이용해서 (i, Hi)와 (i+1, Hi+1)을 연결하는 선분으로 나타낼 수 있다.
수면의 높이가 h라면, 수족관의 바닥과 y=h 사이의 모든 공간이 물로 채워지게 된다. 만약, h보다 높은 바닥이 있다면, 그 곳은 섬이다.
상근이는 설정에서 수족관 바닥 좌표와 수면의 높이를 바꿀 때 마다 물로 채워지는 곳의 넓이를 구하려고 한다.
첫째 줄에 두 양의 정수 N과 상근이가 설정을 바꾼 횟수 M이 주어진다. (3 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
둘째 줄에는 N개의 정수 바닥의 초기 높이 Hi가 공백으로 구분되어 주어진다. (0 ≤ Hi ≤ 1000)
다음 M개 줄에는 상근이가 설정에서 무엇을 바꾸었는 지가 주어진다.
Q h는 수면의 높이를 h로 바꾸었다는 뜻이다. (0 ≤ h ≤ 1000)
U i h는 x좌표가 i인 곳의 바닥의 높이를 h로 바꾸었다는 뜻이다. (0 ≤ i ≤ N-1, 0 ≤ h ≤ 1000) 즉, Hi = h
Q로 시작하는 변경이 주어질 때 마다, 물로 채워지는 곳의 넓이를 소수점 셋째 자리까지 출력한다.
3 2 20 20 20 Q 20 Q 30
0.000 20.000
3 5 0 2 0 Q 2 U 1 1 Q 1 U 1 10 Q 5
2.000 1.000 2.500
7 7 0 2 1 3 2 1 0 Q 1 Q 2 Q 3 U 3 0 Q 1 Q 2 Q 3
0.750 3.750 9.000 1.500 6.000 12.000
왼쪽 그림은 입력으로 주어졌을 때의 상태이며, 오른쪽 그림은 U로 시작하는 설정 변경을 수행한 뒤의 모습이다.