Mộng tưởng của Nếch

Points: 3.5

Time limit: 0.5s

Memory limit: 98M

Author:

Problem type

Cho $N$ cây cột, trong đó cột thứ $i$ có độ cao là $h [i]$ .

Có một chú ếch xanh tên là $N ế c h$ , chú luôn ước mơ được nhảy vút lên chạm tới bầu trời cao rộng. Vì vậy, mỗi khi đứng trên những cây cột, $N ế c h$ chỉ chọn nhảy tới cây cột gần nhất có chiều cao lớn hơn nơi chú đang đứng. Tuy nhiên, cuộc sống không bao giờ dễ dàng như những ước mơ của $N ế c h$ . Leo lên càng cao thì té xuống càng đau, nhưng điều quan trọng nhất là sau mỗi lần vấp ngã, liệu $N ế c h$ có đủ sức mạnh để tự mình đứng dậy và tiếp tục hành trình hay không...

Chú ý, nếu có $2$ cột cao hơn cột hiện tại và xa như nhau thì $N ế c h$ sẽ chọn cột cao hơn.

Với $Q$ truy vấn, cho $x$ là vị trí xuất phát và $k$ là số lần nhảy tối đa. Hãy tính độ cao lớn nhất mà $N ế c h$ có thể đạt được.

Đầu vào

Dòng đầu gồm 2 số nguyên $N$ và $Q$ là số lượng cột và số truy vấn $(1 \leq Q \leq N \leq 10^{5})$ .

Dòng thứ hai ghi $N$ số nguyên dương là độ cao các cột của dãy $h$ , độ cao mỗi cột không quá $10^{9}$ .

$Q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $x$ và $k$ là vị trí xuất phát và số lần nhảy tối đa $(1 \leq x, k \leq N)$ .

Đầu ra

Gồm $Q$ dòng, mỗi dòng là độ cao tối đa mà $N ế c h$ có thể đạt được.

Ví dụ

Đầu vào

Copy

Đầu ra

Copy

Comments

0

kenshiyonezu commented on Oct. 16, 2024, 3:31 p.m.

bài này code bằng dùng thuật toán gì anh nhỉ

0

SonLu_CNTT2_K64 commented on Oct. 16, 2024, 3:39 p.m.

Thử code r tham khảo bài này trước e nhé

0

Ryze commented on Oct. 16, 2024, 10:32 a.m.

kbt test sai k a ...

0

SonLu_CNTT2_K64 commented on Oct. 16, 2024, 10:44 a.m.

Test ví dụ đúng mà nhỉ :?

0

Ryze commented on Oct. 16, 2024, 11:31 a.m.

y la bo test co a :v

0

NguyenHaKien_CNTT4_K63 commented on Oct. 16, 2024, 2:00 p.m.

tớ nghĩ là không sai đâu...

-2

NguyenManhHung_CNTT4_K63 commented on Nov. 3, 2024, 1:08 p.m.

đúng rồi, test không sai cậu sai

0

Ryze commented on Oct. 16, 2024, 2:12 p.m.

vi du ma 2 cot xa nhu nhau ma do cao cung bang nhau thi chon ben nao v a

0

NguyenHaKien_CNTT4_K63 commented on Oct. 16, 2024, 2:18 p.m.

nó nhảy bên nào để sau tối đa k bước nó đạt được độ cao lớn nhất là được =)))

1

Ryze commented on Oct. 16, 2024, 2:25 p.m.

a oke t cam on a ;)