Tập hợp của Schrödinger

View as PDF

Submit solution

Points: 0.01 (partial)
Time limit: 0.75s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Lưu ý: bài có giới hạn thời thời gian không bình thường.

Tập ~S~ là một tập hợp chứa các số nguyên không âm. Tập hợp này có một tính chất đặc biệt là nó có thể mang nhiều trạng thái chồng lập khác nhau sau mỗi biến đổi. Để giải thích kĩ hơn ta có thể nhìn vào hai thao tác biến đổi ~S~ sau:

  • "-"  – xóa đi một phần tử của ~S~.

    • Ví dụ với tập ~S~ đang có duy nhất 1 trạng thái, và đang chứa phần tử ~\lbrace 1, 2, 3 \rbrace~, sau một thao tác "-", ~S~ có thể có 3 trạng thái là ~\lbrace 1, 2 \rbrace~, ~\lbrace 2, 3 \rbrace~ và ~\lbrace 1, 3 \rbrace~.

    • Nếu ta tiếp tục áp dụng thêm một thao tác "-" vào tập hợp, ~S~ lúc này sẽ có các trạng thái là ~\lbrace 1 \rbrace~, ~\lbrace 2 \rbrace~ và ~\lbrace 3 \rbrace~.

  • "+ ~x~"  – thêm phần tử ~x~ vào ~S~.

    • Ví dụ, nếu như ~S~ đang có trạng thái ~\lbrace 1 \rbrace~ và ~\lbrace 2 \rbrace~, nếu ta áp dụng thao thao tác "+ 3", tập ~S~ sẽ mang các trạng thái ~\lbrace 1, 3 \rbrace~ và ~\lbrace 2, 3 \rbrace~.

    • Nếu như ta tiếp tục áp dụng thêm thao tác "+ ~1~", lúc này tập ~S~ sẽ mang các trạng thái ~\lbrace 1, 3 \rbrace~ và ~\lbrace 1, 2, 3 \rbrace~.

Hai thao tác trên có thể được kết hợp với nhau để tập ~S~ có nhiều trạng thái khác nhau. Ngoài ra khi áp dụng thao tác "-" vào ~S~, nếu hiện tại ~S~ đang có một trạng thái là rỗng thì trạng thái này sẽ được bỏ qua.

Ban đầu ~S~ có duy nhất một trạng thái là rỗng. Hãy thực hiện ~q~ truy vấn với tập ~S~, mỗi truy vấn thuộc một trong 3 thao tác sau:

  • "+ ~x~"  – thao tác thêm phần tử vào ~S~;

  • "-"  – thao tác xóa một phần tử khỏi ~S~;

  • "? ~k~"  – hãy tìm số ~x~ lớn nhất có thể sao cho tồn tại một trạng thái của ~S~ mà ~x~ là phần tử lớn thứ ~k~ trong trạng thái đó, hoặc chỉ ra rằng không có trạng thái nào có ít nhất ~k~ phần tử.

Input

Dòng đầu tiên chứa một số tự nhiên ~q~ (~1 \le q \le 200\,000~)  – số truy vấn cần xử lý.

Mỗi dòng trong ~q~ dòng tiếp theo sẽ thuộc một trong ba dạng sau:

  • "+ ~x~" (~1 \le x \le 200\,000~) – thao tác thêm phần tử vào ~S~.

  • "-' – thao tác xóa phần tử khỏi ~S~.

  • "? ~k~" (~1 \le k \le 10~) – truy vấn tìm số ~x~ lớn nhất có thể sao cho tồn tại một trạng thái của ~S~ mà ~x~ là phần tử lớn thứ ~k~ trong trạng thái đó.

Dữ liệu đảm bảo rằng tại mọi thời điểm, ~S~ lúc nào cũng có ít nhất một trạng thái.

Output

Với mỗi truy vấn loại "? ~k~", hãy in ra số ~x~ lớn nhất có thể sao cho tồn tại một trạng thái của ~S~ mà ~x~ là phần tử lớn thứ ~k~ trong trạng thái đó, hoặc in ra ~-1~ nếu không tồn tại trạng thái nào có ít nhất ~k~ phần tử.

Scoring

Subtask Điểm Giới hạn
1 ~500~ Không có hai sự kiện thêm quà nào có cùng giá trị ~x~.
2 ~750~ ~k = 1~
3 ~750~ ~k \le 5~
4 ~1250~ Không có ràng buộc gì thêm.
Tổng ~3250~

Sample Input 1

10
+ 5
+ 4
? 2
? 1
-
+ 5
? 2
? 1
-
? 2

Sample Output 1

4
5
4
5
-1

Sample Input 2

7
+ 3
+ 2
-
? 1
+ 3
-
? 1

Sample Output 2

3
3

Notes

Với ví dụ thứ nhất:

  • Sau hai thao tác đầu tiên, tập ~S~ sẽ có duy nhất một trạng thái là ~\lbrace 4, 5 \rbrace~

  • Tại truy vấn ? 2 đầu tiên, trạng thái duy nhất của ~S~ là ~\lbrace 4, 5 \rbrace~ có phần tử lớn thứ ~k = 2~ là ~4~, do đó đáp án là ~4~.

  • Tại truy vấn ? 1 ngay sau đó, tập ~S~ chưa có thay đổi gì. Đáp án là ~5~.

  • Tại truy vấn - đầu tiên, ~S~ sẽ mang các trạng thái ~\lbrace 4 \rbrace~ và ~\lbrace 5 \rbrace~.

  • Tại truy vấn + 5 ngay sau đó, ~S~ sẽ mang các trạng thái ~\lbrace 4, 5 \rbrace~ và ~\lbrace 5 \rbrace~.

  • Tại truy vấn ? 2 tiếp đó, ~S~ có duy nhất một trạng thái có hai phần tử là ~\lbrace 4, 5 \rbrace~. Đáp án là ~4~ do ~4~ là phần tử lớn thứ ~k = 2~ trong trạng thái này.

  • Tại truy vấn ? 1, cả hai trạng thái của ~S~ đều có phần tử lớn nhất là ~k = 5~.

  • Sau truy vấn - thứ hai, ~S~ sẽ không có trạng thái nào có ít nhất ~2~ phần tử, nên truy vấn ? 2 cuối cùng có đáp án là ~-1~.

Với ví dụ thứ hai:

  • Sau hai thao tác đầu tiên, tập ~S~ sẽ có duy nhất một trạng thái là ~\lbrace 2, 3 \rbrace~

  • Tại truy vấn - tiếp đó, tập ~S~ sẽ có các trạng thái ~\lbrace 2 \rbrace~ và ~\lbrace 3 \rbrace~.

  • Tại truy vấn ? 1 đầu tiên, trạng thái có phần tử lớn thứ ~k = 1~ lớn nhất là trạng thái ~\lbrace 3 \rbrace~. Đáp án là ~3~.

  • Tại truy vấn + 3 sau đó, tập ~S~ sẽ có các trạng thái ~\lbrace 2, 3 \rbrace~ và ~\lbrace 3 \rbrace~.

  • Tại truy vấn - sau đó, tập ~S~ sẽ có các trạng thái ~\lbrace 2\rbrace~, ~\lbrace 3 \rbrace~ và ~\lbrace \rbrace~ (trạng thái rỗng).

  • Tại truy vấn ? 1 cuối cùng, đán án là ~3~. Trạng thái có phần tử lớn thứ ~k = 1~ lớn nhất là ~\lbrace 3 \rbrace~.


Comments

Please read the guidelines before commenting.