TLE-oj Cup Round 8 - Trung vị

Điểm: 1100 (thành phần)

Thời gian: 1.5s

Bộ nhớ: 128M

Input: MEDIAN.inp

Output: MEDIAN.out

Tác giả:

Sunlight, haiender288

Dạng bài

Cho một dãy $A$ ban đầu rỗng. Bạn cần thực hiện $q$ truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

$+\ u$ : thêm phần tử $u$ vào dãy $a$ . $(u \ge 0)$
$-\ u$ : xóa phần tử $u$ khỏi dãy $a$ . Dữ liệu vào đảm bảo dãy $a$ tồn tại phần tử $u$ .

Sau mỗi truy vấn, bạn cần in ra trung vị của dãy $A$ . Trung vị của một dãy $C$ có $n$ phần tử là phần tử lớn thứ $[\frac{n + 1}{2}]$ của dãy $C$ . Nếu dãy $A$ rỗng in ra $-1$ .

Input, Output và Subtasks

Input: (MEDIAN.inp)

Dòng đầu tiên gồm số nguyên dương $q$ . $(q \le 1000000)$
$q$ dòng tiếp theo, mỗi dòng có dạng $+ u_i$ hoặc $- u_i$ miêu tả truy vấn thứ $i$ . $(u_i \le 10^9)$ .

Output: (MEDIAN.out)

Với mỗi truy vấn, in ra trung vị của dãy $A$ .

Subtasks

Subtask 1 $(20\%)$ : $u_i \le 100$ .
Subtask 2 $(20\%)$ : $q \le 1000$ .
Subtask 3 $(20\%)$ : $q \le 10000$ .
Subtask 4 $(20\%)$ : $q \le 100000$ .
Subtask 5 $(20\%)$ : Không có giới hạn gì thêm.

Sample

Input (MEDIAN.inp)

5

+ 1
+ 2
+ 3
+ 4
- 2

Output (MEDIAN.out)

Note

Sau truy vấn đầu tiên: $A = (1)$ và có trung vị là $1$ .
Sau truy vấn thứ hai: $A = (1, 2)$ và có trung vị là $1$ .
Sau truy vấn thứ ba: $A = (1, 2, 3)$ và có trung vị là $2$ .
Sau truy vấn thứ tư: $A = (1, 2, 3, 4)$ và có trung vị là $2$ .
Sau truy vấn thứ năm: $A = (1, 3, 4)$ và có trung vị là $3$ .

Bình luận đầu tiên

Bình luận

Không có bình luận nào.