Đội Hình Hoàn Hảo
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Để chuẩn bị cho giải đấu LQDOJ Cup 2026, ban tổ chức quyết định chọn ra một đội hình gồm các lập trình viên xuất sắc. Có \(n\) ứng viên được xếp thành một hàng ngang, ứng viên thứ \(i\) có năng lực được đánh giá bằng một số nguyên \(a_i\).
Ban tổ chức muốn chọn ra một phân đoạn liên tiếp các ứng viên từ vị trí \(l\) đến vị trí \(r\) (\(1 \le l \le r \le n\)) sao cho đội hình này "hoàn hảo". Một đội hình được gọi là hoàn hảo nếu chênh lệch giữa năng lực của người giỏi nhất và người kém nhất trong đoạn đó không vượt quá một giá trị \(k\) cho trước. Nghĩa là:
\[\max(a_l, a_{l+1}, \dots, a_r) - \min(a_l, a_{l+1}, \dots, a_r) \le k\]
Đồng thời, ban tổ chức có \(q\) câu hỏi, mỗi câu hỏi yêu cầu bạn tìm độ dài lớn nhất của một đội hình hoàn hảo nằm trọn trong đoạn \([L, R]\) cho trước.
Input
- Dòng đầu tiên chứa ba số nguyên \(n, k, q\) (\(1 \le n, q \le 2 \cdot 10^5, 0 \le k \le 10^9\)).
- Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) biểu diễn năng lực của các ứng viên.
- \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le n\)) mô tả một truy vấn.
Output
- Ghi ra \(q\) dòng, mỗi dòng là một số nguyên duy nhất là câu trả lời cho truy vấn tương ứng.
Example
Test 1
Input
5 2 3
1 5 4 3 8
1 3
2 4
1 5Output
2
3
3Note
- Truy vấn 1 (\([1, 3]\)): Đoạn hoàn hảo dài nhất là \([2, 3]\) (gồm các phần tử \(5, 4\) có chênh lệch \(5 - 4 = 1 \le 2\)). Độ dài là \(2\).
- Truy vấn 2 (\([2, 4]\)): Đoạn hoàn hảo dài nhất là \([2, 4]\) (gồm các phần tử \(5, 4, 3\) có chênh lệch \(5 - 3 = 2 \le 2\)). Độ dài là \(3\).
- Truy vấn 3 (\([1, 5]\)): Đoạn hoàn hảo lớn nhất vẫn là \([2, 4]\) có độ dài \(3\).
Bình luận