h991: 確實大師 (Chesh Master)
Tags : 數學
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-19 19:04

Content

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

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

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

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

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

Input

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

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

  • $1 \leq n \leq 2\times 10^5$
  • $1 \leq ty \leq 2$
  • $-10^8 \leq x, y, z \leq 10^8$
Output

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

Sample Input #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
Sample Output #1
-1
36
36
36
36
29
29
29
29
29
36
36
36
36
36
36
36
36
34
34
測資資訊:
記憶體限制: 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
Hint :

$5\%:n \leq 1000$

$95\%:無特別限制$

Tags:
數學
出處:
第六屆簡單的小競賽 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」