Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMQUABEO - Quá béo

Cân nặng đã ở mức đáng báo động, admin K quyết định tập chạy để giảm cân. Khu vực admin K sống có một con đường dài, điểm đầu của con đường là điểm 0, điểm cuối của con đường là điểm N-1. Các điểm cách đều nhau một khoảng 1 đơn vị độ dài; điểm thứ i có độ cao H[i]. Admin K muốn chọn ra một đoạn đường để tập chạy sao cho:

  • Đoạn đường có chiều dài ít nhất là L.
  • Chênh lệch độ cao giữa điểm cao nhất và điểm thấp nhất trên đoạn đường không vượt quá D.

Bạn hãy giúp xác định xem có bao nhiêu đoạn đường thỏa mãn.

Input

  • Dòng đầu tiên ghi ba số N L D.
  • Dòng thứ hai ghi N số H[i] là độ cao của điểm thứ i.

Output

In ra số đoạn đường thỏa mãn.

Giới hạn

 

  • 1 <= L < N <= 10^6
  • 0 <= D <= 10000
  • 1 <= H[i] <= 10000
  • Trong 15% số test, N <= 500
  • Trong 20% số test tiếp theo, N <= 10^4
  • Trong 25% số test tiếp theo, N <= 10^5

 

Example

Input:
10 3 4
5 6 9 7 4 3 5 6 8 8

Output:
5

Được gửi lên bởi:VOJ Team
Ngày:2014-07-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Marathon 2014

hide comments
2019-07-04 02:57:23
O(n) AC :))
2019-02-27 06:59:47
deque AC
2018-08-04 15:29:55
giống bài kdiff
2018-05-23 03:05:05
nhật hào bẩn
2017-12-21 09:42:12
Khá EZ
Đê mờ quên long long 2 đấm AC=.=
( F*CK !!!!)
\/
-O
/|\
-/\
frostpixel aka.How 2 AC

Last edit: 2017-12-21 09:43:01
2017-11-22 09:54:42
nhật hào sạch
2017-11-22 01:38:58
có ai dùng Min/Max tịnh tiến đc AC chưa giúp e vs sao nó 96 miết thôi
2017-11-17 12:16:15
Ai GT cho minh test de bai vs.
thank nh
2017-11-16 04:29:52
có bác nào chặt full ko? :v
2016-12-30 19:16:35
nlogn mà ko ac là sao sao sao ==
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.