View Code of Problem 3572

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define Max 100010
int a[Max];
int max[Max];
int min[Max];

int main()
{
    int t;
    int n,k;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        int i,j;
        int w=0;
        int sum=0;
       // memset(max,-1,sizeof(max));
       // memset(min,-1,sizeof(min));
        for(i=0;i<n;i++){
            scanf("%d",a+i);
            //printf("a[i]=%d\n",a[i]);
            for(j=i-1;j>=w;j--){
                if(fabs(max[j]-a[i])>=k||fabs(min[j]-a[i])>=k){
                    w=j+1;
                    break;
                }
                if(max[j]<a[i])
                    max[j] = a[i];
                if(min[j]>a[i])
                    min[j] = a[i];
                sum++;
            }
           // printf("w=%d\n",w);
           // printf("sum=%d\n",sum);
            max[i] = min[i] = a[i];
        }
        printf("%d\n",sum+n);
    }
    //printf("Hello world!\n");
    return 0;
}

Double click to view unformatted code.


Back to problem 3572