h991. 確實大師 (Chesh Master) - 高中生程式解題系統

內容

確實小子 ( $Chesh Boy$ ) 平常遇到什麼事都會說「確實」，像是有人對他說他很煩，他會說「確實」；有人問他晚餐要吃什麼，他也會說「確實」。

只是如果所有問題他都說確實就不太好了，如果要表達否定，確實小子會說「不確實」。像是有一次肯肯肯在練習砍樹，他問確實小子他砍得如何，確實小子說「不確實」，於是肯肯肯發憤圖強，之後拿到 $OIO (International Olympiad in Tree Chopping)$ 的滿分金。

確實小子的夢想是成為「確實大師」( $Chesh Master$ )，只是在此之前，他得去「確實賣場」( $Chesh Mart$ ) 買東西。他在「確實賣場」遇到了他的好友「確實怪」( $Chesh Monster$ )，「確實怪」身上有很多點讓他感到很確實，如果把這些點以三維座標表示，每個點都可以寫作整數點 $(x, y, z)$ ，而「確實怪」的「確實度」則是「確實怪」身上所有點中兩個點曼哈頓距離的最大值，也就是找得到兩個不同編號 $i, j$ ， $| x_{i} - x_{j} | + | y_{i} - y_{j} | + | z_{i} - z_{j} |$ 為最大。

確實小子可以在確實怪身上加入更多點，或是移除一些點，每次加入或移除時，請你幫確實小子找出確實怪的確實度。

如果你幫了確實小子的忙，他會對你說「確實」的。

輸入說明

第一行有一個整數 $n$ ，代表有幾筆操作。

接下來 $n$ 行，每行有四個整數 $t y, x, y, z$ ，若 $t y = 1$ ，代表確實怪身上多了 $(x, y, z)$ 這個點，保證確實怪在此操作前，身上沒有 $(x, y, z)$ 這個點；若 $t y = 2$ ，代表確實怪身上少了 $(x, y, z)$ 這個點，保證確實怪在此操作前，身上有 $(x, y, z)$ 這個點。

$1 \leq n \leq 2 \times 10^{5}$
$1 \leq t y \leq 2$
$- 10^{8} \leq x, y, z \leq 10^{8}$

輸出說明

對於每筆操作，輸出目前確實怪身上兩個點最遠的曼哈頓距離。若確實怪身上的點數小於 $2$ ，輸出 $- 1$ 。

範例輸入 #1

20
1 -8 -2 -10
1 4 -7 9
1 -5 6 7
1 3 -4 5
1 7 -6 2
2 -8 -2 -10
2 4 -7 9
2 3 -4 5
1 -1 -8 -2
1 5 1 1
1 -7 8 10
1 -3 -9 7
1 8 4 -1
1 -1 -10 10
1 -5 -9 1
1 -8 -9 2
1 -1 1 -10
1 -2 5 -8
2 7 -6 2
1 4 8 3

範例輸出 #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 3.0s , <1M
公開測資點#1 (15%): 3.0s , <10M
公開測資點#2 (16%): 3.0s , <10M
公開測資點#3 (16%): 3.0s , <10M
公開測資點#4 (16%): 3.0s , <10M
公開測資點#5 (16%): 3.0s , <10M
公開測資點#6 (16%): 3.0s , <10M

提示：

$5 % ： n \leq 1000$

$95 % ：無特別限制$

標籤:

數學

出處:

第六屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」