TLEoj Contest #04 - I hate sqrt - TLEOJ: TLE Online Judge

TLEoj Contest #04 - I hate sqrt

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

Thời gian: 2.0s

Bộ nhớ: 1G

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Lời thách đấu của Kaito huyhau6a2 the Kid tới Edogawa Sunlight

Ta đã bắt cóc bạn gái của ngươi là aisukiuwu Ran (có hình ảnh minh họa)

Image

8 giờ tối nay, vào đêm trăng (tròn hay không không quan trọng), hãy đến quảng trường TLE. Chúng ta hãy thách đấu với nhau trên quảng trường đó. Nếu ngươi thắng, ta sẽ thả bạn gái của ngươi ra và sẽ cho ngươi 200k để đi chơi với người yêu. Chúng ta cùng thách đấu nào!

Kaito huyhau6a2 the Kid

Đó chính là lời thách đấu của Kaito huyhau6a2 the Kid tới Edogawa Sunlight. Edogawa Sunlight sau khi biết được tin này đã rất hoảng loạn, cậu ta đã chuẩn bị món quà nhỏ nhỏ xinh xinh nhân ngày kỷ niệm hơn 9 tháng yêu nhau cùng với aisukiuwu Ran rồi. Vậy mà lại xảy ra cơ sự như thế này. Nhưng đây biết đâu lại là cơ hội, vì nếu cậu ta cứu được aisukiuwu Ran thì sẽ có cơ hội tỏ tình với cô ấy. Thế là vào đúng lúc 8 giờ tối hôm ấy, cậu lướt ván trượt nhanh như bay, và đã tới được nơi mà Kaito huyhau6a2 the Kid thách đấu. Ở đấy đã có rất nhiều người theo dõi, trên ti vi cũng live trận thách đấu của cậu ta. Từ trước giờ, cậu chưa bao giờ gặp trận thách đấu nào căng thẳng đến như thế này, nhưng mà vì aisukiuwu Ran, cậu không thể dừng lại được. Trận đấu bắt đầu!

Kaito huyhau6a2 the Kid quyết định thách đấu với Edogawa Sunlight bằng cách là mỗi người sẽ ra 1 bài toán cho đối phương giải. Edogawa Sunlight ra bài trước, nhưng mà Kaito huyhau6a2 the Kid rất nhanh đã giải được chỉ trong vòng $27022009\ ms$ (ăn may :D). Tới luợt Kaito huyhau6a2 the Kid ra bài. Ra bài xong, sau một thời gian, Edogawa Sunlight đã nghĩ ra thuật, nhưng mà... "Chắc chưa?" - một câu hỏi đơn giản đã làm Edogawa Sunlight phải toát mồ hôi hột. Vì thế xin nhờ các bạn hãy cùng Edogawa Sunlight giải bài toán này nhé! Nếu bạn giải được bài toán này cho Edogawa Sunlight thì sẽ được tặng vé xem phim Tàu ngầm sắt màu đen mới nhất đang chiếu trên rạp đó! Bài toán như sau:

Ta gọi một dãy số $a$ được gọi là dãy đáng ghét khi có một giá trị $k$ không âm thỏa mãn cả $k$ và $\sqrt k$ đều xuất hiện trong dãy số đó.

Bạn được cho một dãy số $a$ gồm $n$ phần tử. Nhiệm vụ của bạn là thực hiện $q$ truy vấn thuộc 1 trong 2 loại như sau:

$1\ i\ k$ : Đặt $a_i=k$
$2\ l\ r$ : Kiểm tra xem dãy số $a_l,a_{l+1},\dots,a_r$ có phải là dãy số đáng ghét không. Nếu có, nhiệm vụ của bạn là tìm một cặp số $l\le u\le v\le r$ thỏa mãn $a_u=\sqrt {a_v}$ hoặc $a_v=\sqrt {a_u}$ . Ưu tiên xuất giá trị $u$ nhỏ nhất, sau đó tới $v$ nhỏ nhất

Lưu ý là các truy vấn loại 1 sẽ độc lập với nhau, hay nói cách khác, truy vấn loại 1 thứ $i-1$ sẽ hết hiệu lực ngay trước khi thực hiện truy vấn loại 1 thứ $i$

Input, Output và Subtasks

Input

Dòng đầu chứa hai số nguyên dương $n,q\ (1\le n,q\le 5\times 10^5)$ ;
Dòng tiếp theo chứa $n$ giá trị $a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9)$
Sau đó là $q$ dòng, mỗi dòng chứa 1 trong 2 truy vấn được định dạng như trên

Output

Với mỗi truy vấn loại 2, xuất ra kết quả trên một dòng. Trường hợp dãy số $a_l,a_{l+1},\dots,a_r$ không phải là dãy số đáng ghét, hãy xuất -1, ngược lại, hãy xuất ra 2 số $u,v$ thỏa mãn theo yêu cầu.

Scoring

Subtask 1 ( $20\%$ ): $n,q\le 500$
Subtask 2 ( $20\%$ ): $n,q\le 5000$
Subtask 3 ( $20\%$ ): Không có truy vấn loại 1
Subtask 4 ( $20\%$ ): $n,q\le 10^5$
Subtask 5 ( $20\%$ ): Không có ràng buộc gì thêm

Sample

Input

Output

Note

Dãy $a$ ban đầu: $3,2,4,6,9$
Trong truy vấn 1, cặp số thỏa mãn là $(1,5)$ vì $3=\sqrt 9$
Trong truy vấn 2, cặp số thỏa mãn là $(2,3)$ vì $2=\sqrt 4$
Trong truy vấn 3, dãy số $a$ được đặt lại thành $3,2,36,6,9$
Trong truy vấn 4, cặp số thỏa mãn là $(3,4)$ vì $6=\sqrt {36}$
Trong truy vấn 5, dãy số $a$ được đặt lại thành $3,2,4,6,10$
Trong truy vấn 6, cặp số thỏa mãn là $(2,3)$ vì $2=\sqrt 4$

Bình luận

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