TopCoder

User's AC Ratio

94.4% (17/18)

Submission's AC Ratio

70.8% (51/72)

Tags

Description

廢話不多說(X),請你維護一個集合 $P$ ,一開始集合為空,所有操作都在一維的數線上。現在給你 $N$ 個操作,操作有三種:

  1. insert $x$:加入一點座標為 $x$ 到當前的集合內。
  2. delete $x$ :從集合內將點座標為 $x$ 的點刪除,該操作出現時保證點 $x$ 已經在集合內。
  3. query $x$:詢問在目前集合中,距離座標 $x$ 最近的點座標為多少,請輸出一行包含一個整數代表距離 $x$ 最近的點座標;若同時存在兩個不同的座標距離 $x$ 一樣近,請輸出這兩個座標,較小的先輸出。詢問時保證集合內至少有一個點。

Input Format

輸入的第一行包含一個整數 $N\,(N \leq 10 ^ 5)$,代表接下來有 $N$ 筆操作。操作的格式前面題目敘述所述。

保證 $|x| \leq 10 ^ 9$,測資是隨機產生的,你可以假設你產生的二元樹不會不夠平衡。

Output Format

遇到操作為 query $x$ 時輸出一行詢問的結果。

Sample Input 1

7
insert 4
insert 10
insert 5
query 7
delete 5
query 7
query 10

Sample Output 1

5
4 10
10

Hints

Problem Source

NEOJ Problem 47

Subtasks

No. Testdata Range Constraints Score
1 0~2 $N\leq 1000$ 30
2 3~9 無額外限制。 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 2
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2