시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1536 MB | 106 | 33 | 29 | 39.189% |
2차원 평면 위에 정수점들의 중복집합(multiset)인 $U$와 $V$가 있다.
두 중복집합 $U, V$가 주어졌을 때, 다음의 값 $D(U, V)$를 생각할 수 있다.
$$D(U, V) = \min_{u \in U, v \in V} \left( \max (u_x+v_x, u_y+v_y)\right)$$
처음에 $U$와 $V$는 모두 비어 있다. 편의상 $U$ 또는 $V$가 비어 있는 경우 $D(U,V)$값은 $-1$로 정의하도록 하자. 이제 쿼리를 통해 $U$와 $V$에 정수점이 자유롭게 추가되거나 제거된다. 변화가 일어날 때 마다 $D(U,V)$를 계산하는 프로그램을 작성하도록 하자.
중복집합에 점을 추가하는 쿼리는 1 s x y 와 같이 주어진다. $s=1$인 경우에는 $U$에, $s=2$인 경우에는 $V$에 점 $(x,y)$를 추가하라는 의미이다.
중복집합에 점을 제거하는 쿼리는 2 s x y 와 같이 주어진다. $s=1$인 경우에는 $U$에서, $s=2$인 경우에는 $V$에서 점 $(x,y)$를 제거하라는 의미이다.
$U$와 $V$는 각각 중복집합이므로, 점이 추가될 때 이미 존재하는 점이 추가될 수도 있다.
$U$와 $V$에서 점을 제거할 때 이미 동일한 좌표를 가지는 점이 여러 개 존재하는 경우, 그 중 하나만 없애는 것으로 처리한다. 존재하지 않는 점을 제거하는 쿼리는 주어지지 않는다.
입력의 첫 줄에 쿼리의 개수를 나타내는 $q$가 주어진다.
이후 $q$개의 줄에 걸쳐 쿼리를 나타내는 정수 r s x y가 주어진다.
$q$개 줄에 각 쿼리를 실행한 직후의 $D(U,V)$값을 출력한다.
두 집합 중 하나라도 비어 있는 경우 $D(U,V) = -1$임에 유의하라.
6 1 1 100 100 1 2 30 130 1 1 120 170 2 1 100 100 1 2 70 100 2 1 120 170
-1 230 230 300 270 -1