GCD2

Tác giả:

Dạng bài

Điểm: 400 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một tập hợp rỗng, bạn sẽ lần lượt thực hiện N thao tác. Có hai loại thao tác được thực hiện:

Thao tác 1 có dạng \((1, x)\) : thêm số \(x\) vào tập hợp.
Thao tác 2 có dạng \((2, x)\): loại bỏ một số \(x\) ra khỏi tập hợp, dữ liệu luôn đảm bảo tồn tại ít nhất một số \(x\) trước khi thực hiện thao thao tác này.

Sau mỗi lần thực hiện thao tác, hãy đưa ra ước chung lớn nhất của tập hợp này. Với trường hợp tập hợp con rỗng hãy in ra số \(1\).

Dòng đầu tiên một số tự nhiên \(N\) (\(1 \leq N \leq 10^{5}\)).
\(N\) dòng tiếp theo, mỗi dòng là gồm 2 số \(t\) và \(x\) với \(t\) là loại thao tác và \(x\) là số cần được xử lí (\(1 \leq t \leq 2\), \(1 \leq x \leq 10^{9}\)).

Gồm \(N\) dòng là ước chung lớn nhất của tập hợp sau mỗi lần thực hiện một thao tác.

Test 1

Input

Output

Bình luận

2

Vinht1k60 12:41 a.m. 18 Tháng 8, 2020

Sau bài này chả ai code thuật chuẩn mà cũng ac được nhỉ ?

0

hhoangcpascal 7:25 a.m. 18 Tháng 8, 2020

Thuật chuẩn bài này chỉ có nén + Segment Tree thôi mà :V

0

Vinht1k60 10:49 a.m. 18 Tháng 8, 2020

Thì thế mới hỏi không ai code Segment hết nhưng vẫn AC :v

0

Vinht1k60 10:54 a.m. 18 Tháng 8, 2020

Đùa chứ trông for cái map xong rồi là đánh dấu cái map mà vẫn qua được ,quá là tài tình @@