Trong rừng mưa nhiệt đới Sumatra, có \(N\) cây nằm liên tiếp trên một hàng, được đánh số từ \(0\) đến \(N - 1\) theo thứ tự từ trái sang phải. Tất cả các cây có chiều cao đôi một khác nhau; cây \(i\) có chiều cao \(H[i]\).

Pak Dengklek đang huấn luyện một con đười ươi nhảy từ cây này sang cây khác. Trong một lần nhảy, đười ươi có thể nhảy từ ngọn cây hiện tại sang ngọn cây gần nhất ở bên trái hoặc bên phải có chiều cao lớn hơn cây hiện tại. Cụ thể, nếu đười ươi đang ở cây \(x\), nó có thể nhảy sang cây \(y\) khi và chỉ khi một trong hai điều sau được thỏa mãn:

• \(y\) là số nguyên không âm lớn nhất nhỏ hơn \(x\) sao cho \(H[y] > H[x]\); hoặc
• \(y\) là số nguyên không âm nhỏ nhất lớn hơn \(x\) sao cho \(H[y] > H[x]\).

Pak Dengklek có \(Q\) phương án tập nhảy. Mỗi phương án được biểu diễn bằng bốn số nguyên \(A\), \(B\), \(C\) và \(D\) (\(A \le B < C \le D\)). Với mỗi phương án, Pak Dengklek muốn biết liệu đười ươi có thể bắt đầu tại một cây \(s\) nào đó (\(A \le s \le B\)) và kết thúc tại một cây \(e\) nào đó (\(C \le e \le D\)) bằng một dãy các bước nhảy hay không. Nếu có thể, Pak Dengklek muốn biết số bước nhảy ít nhất mà đười ươi cần thực hiện cho phương án đó.

Chi tiết cài đặt

Thí sinh cần cài đặt hai hàm sau:

void init(int N, std::vector<int> H);

• \(N\): số lượng cây.
• \(H\): mảng độ dài \(N\), trong đó \(H[i]\) là chiều cao của cây \(i\).
• Hàm này được gọi đúng một lần, trước mọi lời gọi đến hàm minimum_jumps.
• Hàm này không trả về giá trị.

int minimum_jumps(int A, int B, int C, int D);

• \(A\), \(B\): phạm vi các cây mà đười ươi được phép bắt đầu.
• \(C\), \(D\): phạm vi các cây mà đười ươi được phép kết thúc.
• Hàm phải trả về số bước nhảy ít nhất để hoàn thành phương án, hoặc trả về \(-1\) nếu không thể hoàn thành.
• Hàm này được gọi đúng \(Q\) lần.

Ví dụ

Xét lời gọi sau:

init(7, {3, 2, 1, 6, 4, 5, 7});

Sau khi khởi tạo, xét lời gọi:

minimum_jumps(4, 4, 6, 6);

Đười ươi phải bắt đầu tại cây \(4\) (cao \(4\)) và kết thúc tại cây \(6\) (cao \(7\)). Một cách đạt số bước nhảy ít nhất là trước tiên nhảy đến cây \(3\) (cao \(6\)), rồi nhảy đến cây \(6\). Một cách khác là nhảy đến cây \(5\) (cao \(5\)), rồi nhảy đến cây \(6\). Vì vậy, hàm minimum_jumps phải trả về \(2\).

Xét một lời gọi khác:

minimum_jumps(1, 3, 5, 6);

Đười ươi phải bắt đầu tại cây \(1\) (cao \(2\)), cây \(2\) (cao \(1\)) hoặc cây \(3\) (cao \(6\)), và phải kết thúc tại cây \(5\) (cao \(5\)) hoặc cây \(6\) (cao \(7\)). Cách duy nhất đạt số bước nhảy ít nhất là bắt đầu từ cây \(3\), sau đó nhảy đến cây \(6\) chỉ bằng một lần nhảy. Vì vậy, hàm minimum_jumps phải trả về \(1\).

Xét một lời gọi khác:

minimum_jumps(0, 1, 2, 2);

Đười ươi phải bắt đầu tại cây \(0\) (cao \(3\)) hoặc cây \(1\) (cao \(2\)), và phải kết thúc tại cây \(2\) (cao \(1\)). Vì cây \(2\) là cây thấp nhất nên không thể nhảy đến cây này từ bất kỳ cây nào cao hơn nó. Vì vậy, hàm minimum_jumps phải trả về \(-1\).

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le H[i] \le N\) với mọi \(0 \le i \le N - 1\).
• \(H[i] \ne H[j]\) với mọi \(0 \le i < j \le N - 1\).
• \(0 \le A \le B < C \le D \le N - 1\).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): \(N\ Q\).
• Dòng \(2\): \(H[0]\ H[1]\ \ldots\ H[N - 1]\).
• Dòng \(3 + i\) (\(0 \le i \le Q - 1\)): \(A\ B\ C\ D\) cho lời gọi thứ \(i\) đến hàm minimum_jumps.

Trình chấm mẫu ghi kết quả theo định dạng sau:

• Dòng \(1 + i\) (\(0 \le i \le Q - 1\)): giá trị trả về của lời gọi thứ \(i\) đến hàm minimum_jumps.

7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2

2
1
-1

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2021: Rainforest Jumps.