Dãy con tăng có khoảng cách giới hạn
Xem PDF
Điểm:
1700
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho mảng \(A\) gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) và hai số nguyên \(L, R\) (\(1 \le L \le R\)).
Một dãy con của mảng \(A\) được xác định bởi tập hợp các chỉ số \(1 \le i_1 < i_2 < \dots < i_k \le N\). Dãy con này được gọi là thỏa mãn điều kiện nếu với mọi \(1 \le j < k\), chênh lệch giữa hai phần tử liên tiếp trong dãy con thỏa mãn:
\[L \le a_{i_{j+1}} - a_{i_j} \le R\]
Hãy tìm độ dài lớn nhất \(k\) của một dãy con thỏa mãn điều kiện trên.
Input
- Dòng đầu tiên chứa ba số nguyên \(N, L, R\) (\(1 \le N \le 10^5, 1 \le L \le R \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\)).
Output
- In ra một số nguyên duy nhất là độ dài lớn nhất của dãy con thỏa mãn.
Example
Test 1
Input
6 2 5
3 1 5 8 6 10Output
4Note
Dãy con dài nhất thỏa mãn là \([3, 5, 8]\) tương ứng với các chỉ số \((1, 3, 4)\).
Hiệu giữa các phần tử kề nhau: \(5 - 3 = 2\) và \(8 - 5 = 3\), đều nằm trong đoạn \([2, 5]\).
Scoring
- Subtask 1 (100% số điểm): \(1 \le N \le 10^5, 1 \le L \le R \le 10^9, 1 \le a_i \le 10^9\).
Bình luận (4)