Good subsequence( RMQ+二分)

Description

Give you a sequence of n numbers, and a number k you should find the max length of Good subsequence. Good subsequence is a continuous subsequence of the given sequence and its maximum value - minimum value<=k. For example n=5, k=2, the sequence ={5, 4, 2, 3, 1}. The answer is 3, the good subsequence are {4, 2, 3} or {2, 3, 1}.

Input

There are several test cases.
Each test case contains two line. the first line are two numbers indicates n and k (1<=n<=10,000, 1<=k<=1,000,000,000). The second line give the sequence of n numbers a[i] (1<=i<=n, 1<=a[i]<=1,000,000,000).
The input will finish with the end of file.

Output

For each the case, output one integer indicates the answer.

Sample Input

Sample Output

3
1

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <string>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <stack>
12 #include <sstream>
13 #include <iomanip>
14 using namespace std;
15 const int INF=0x4fffffff;
16 const int EXP=1e-6;
17 const int MS=10005;
18 const int MS2=100005;
19 
20 int a[MS];
21 int n,k;
22 
23 int minv[MS][15];
24 int maxv[MS][15];
25 
26 void RMQ_init()
27 {
28       for(int i=0;i<n;i++)
29       {
30             minv[i][0]=a[i];
31             maxv[i][0]=a[i];
32       }
33 
34       for(int j=1;(1<<j)<=n;j++)
35       {
36             for(int i=0;i+(1<<j)-1<n;i++)
37             {
38                   minv[i][j]=min(minv[i][j-1],minv[i+(1<<(j-1))][j-1]);
39                   maxv[i][j]=max(maxv[i][j-1],maxv[i+(1<<(j-1))][j-1]);
40             }
41       }
42 }
43 
44 int RMQ(int l,int r)
45 {
46       int k=0;
47       while(1<<(k+1)<=r-l+1)
48             k++;
49       return   max(maxv[l][k],maxv[r-(1<<k)+1][k])-min(minv[l][k],minv[r-(1<<k)+1][k]);
50 }
51 
52 int main()
53 {
54 
55       while(scanf("%d%d",&n,&k)!=EOF)
56       {
57             for(int i=0;i<n;i++)
58                   scanf("%d",&a[i]);
59             RMQ_init();
60             int ans=0;
61             for(int i=0;i<n;i++)
62             {
63                   int l=i;
64                   int r=n-1;
65                   while(l<=r)
66                   {
67                         int mid=(l+r)/2;
68                         int t=RMQ(i,mid);
69                         if(t>k)
70                               r=mid-1;
71                         else
72                               l=mid+1;
73                   }
74                   if(ans<l-i)
75                         ans=l-i;
76             }
77             cout<<ans<<endl;
78       }
79       return 0;
80 }