BOJ 31956 MountainCraft

문제 링크:

문제 내용

최초에 비어 있는 평면에 산을 추가하고 제거하는 쿼리가 주어집니다. 매 쿼리마다, 산들이 이루는 맨 위쪽 테두리의 길이를 구하세요.

산은 산꼭대기의 좌표로 정의되며, 산꼭대기를 나타내는 점으로부터 왼쪽으로 기울기가 $1$, 오른쪽으로 기울기가 $-1$인 반직선을 그어 $x$축과 만나는 지점에서 종료됩니다.

입력

첫 줄에는 쿼리의 개수 $q$와 평면의 가로 길이 $w$가 주어집니다. ($1 \le q \le 200\;000$, $1 \le w \le 10^9$) 평면의 $x$좌표는 $0$에서 $w$까지가 됩니다.

다음 $q$줄에는 각각 추가하거나 제거할 산꼭대기의 좌표 $(x, y)$가 주어집니다. ($0 \le x \le w$, $0 < y \le 10^9$) 현재 그 산꼭대기가 존재하지 않는다면 추가하고, 존재한다면 제거합니다.

출력

$q$줄에 걸쳐서 각 쿼리 이후의 문제의 정답을 출력합니다. 실제 정답과 절대 또는 상대 오차가 $10^{-6}$ 이하이면 통과됩니다.

문제 풀이