Subsequence//2010 ACM-ICPC Multi-University Training Contest(10)——Host by HEU

Subsequence
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 28   Accepted Submission(s) : 5
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.
Input
There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.
Output
For each test case, print the length of the subsequence on a single line.
Sample Input

5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5

Sample Output

5
4

Source
2010 ACM-ICPC Multi-University Training Contest(10)——Host by HEU
 
 
#include#include#include#includeusing namespace std;#define maxs( a , b ) a>b?a:b#define mins( a , b ) a>b?b:aconst int MAX_N = 110005;
int d[MAX_N];int dpmin[MAX_N][25];int dpmax[MAX_N][25];int n;
void create_Dpmin(){     int i , j;     for( i = 1 ; i <= n ; i++ )          dpmin[i][0] = d[i];     for( j = 1 ; j <= log((double)(n+1))/log(2.0) ; j++ ){          for( i = 1 ; i+(1<int getmax( int a , int b ){    int k = (int)(log((double)(b-a+1))/log(2.0));    return maxs( dpmax[a][k] , dpmax[b-(1<int getmin( int a , int b ){    int k = (int)(log((double)(b-a+1))/log(2.0));    return mins( dpmin[a][k] , dpmin[b-(1<=m&&temp<=k)            {                int len=i-now+1;                if(len>cnt) cnt=len;            }            else if(temp