Mộng tưởng của Nếch
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ếch\), 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ếch\) 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ếch\). 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ếch\) 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ếch\) 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ếch\) 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 \le Q \le N \le 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 \le x, k \le N)\).
Đầu ra
Gồm \(Q\) dòng, mỗi dòng là độ cao tối đa mà \(Nếch\) có thể đạt được.
Ví dụ
Đầu vào
5 5
1 3 4 2 5
1 1
2 1
3 2
4 1
5 2Đầu ra
3
4
5
5
5
Comments
bài này code bằng dùng thuật toán gì anh nhỉ
Thử code r tham khảo bài này trước e nhé
kbt test sai k a ...
Test ví dụ đúng mà nhỉ :?
y la bo test co a :v
tớ nghĩ là không sai đâu...
vi du ma 2 cot xa nhu nhau ma do cao cung bang nhau thi chon ben nao v a
nó nhảy bên nào để sau tối đa k bước nó đạt được độ cao lớn nhất là được =)))
a oke t cam on a ;)