Max - Min của đoạn
Xem PDF
Điểm:
400
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
là một nhà toán học đại tài, người có chỉ số iq cao nhất nhân loại nếu đếm ngược. Đặc biệt anh rất thích thú với những thứ to và nhỏ, các con số không phải là ngoại lệ. Bởi vậy hôm nay đang thắc mắc một bài toán như sau :
Bạn được cung cấp một dãy số gồm \(n\) số nguyên \(A_1,A_2,...,A_n\).
Nhiệm vụ của bạn là đếm số lượng đoạn con có \(max - min = k\). Ở đây \(max\) và \(min\) là giá trị lớn nhất và giá trị nhỏ nhất của đoạn con đó.
suy nghĩ bài toán này đến mức hói cả đầu mà vẫn chưa nghĩ ra, các bạn hãy giúp nhé !
Input
- Dòng đầu tiên gồm 2 số nguyên \(n,k(0 \le k \le 10^9)\).
- Dòng thứ 2 gồm \(n\) số nguyên \(A_1,A_2,A_3,...,A_n(-10^9 \le A_i \le 10^9)\).
Output
- Gồm một số nguyên duy nhất là số lượng đoạn con thỏa mãn.
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\).
- Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^5\).
- Subtask \(3\) (\(30\%\) số điểm): \(n \le 5 \times 10^5\).
Example
Test 1
Input
5 2
1 2 1 3 3Output
6
Bình luận
=)
Bài này em xài mảng tiền tố dc ko ạ
Ra đề hơi vui hì, algorit ra đề mà kêu algorit không bik làm nhờ các bạn giúp =)))?
sao e bi rte vay :((
bài ni dùng deque hay hơn
a