View Code of Problem 3572

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

typedef long long ll;
#define Max 100010
#define fMax(a,b) (a>b?a:b)
#define fMin(a,b) (a<b?a:b)


int a[Max];
int max[Max];
int min[Max];
int Nmax;
int Nmin;

void build(int dx,int begin,int end){
    if(begin==end){
        max[dx] = min[dx] = a[begin];
        return;
    }
    int m = (begin+end)/2;
    build(dx*2,begin,m);
    build(dx*2+1,m+1,end);
    max[dx] = fMax(max[dx*2],max[dx*2+1]);
    min[dx] = fMin(min[dx*2],min[dx*2+1]);
}

/*void find(int dx,int begin,int end){
    if(begin>=end)
        return;
    Nmax = fMax(Nmax,max[dx]);
    Nmin = fMin(Nmin,min[dx]);
    int m = (begin+end)/2;
    find(dx*2,begin,m);
    find(dx*2+1,m+1,end);
}*/

void search(int dx,int begin,int end,int i,int j){
    if(j<begin||i>end)
        return;
    if(begin>=i&&end<=j){
        Nmax = fMax(Nmax,max[dx]);
        Nmin = fMin(Nmin,min[dx]);
        return;
    }
    int m=(begin+end)/2;
    search(dx*2,begin,m,i,j);
    search(dx*2+1,m+1,end,i,j);
}

int main()
 {
     int T;
     scanf("%d",&T);
     while(T--){
        int n,k;
        //ll sum = 0;
        scanf("%d%d",&n,&k);
        int i,j;
        ll sum = 0;
        for(i=1;i<=n;i++)
            scanf("%d",a+i);
        build(1,1,n);
        for(i=1;i<=n;i++){
            Nmax = -1;
            Nmin = 9999999;
            search(1,1,n,i,n);
            if(Nmax-Nmin<k)
                    sum += n-i+1;
            else{
            //    printf("jaja\n");
                Nmax = Nmin = a[i];
                for(j=i;j<n;j++){
                   if(Nmax-Nmin>=k)
                        break;
                  Nmax = fMax(Nmax,a[j+1]);
                  Nmin  = fMin(Nmin,a[j+1]);
                   sum++;
                }
            }
           // printf("sum=%lld\n",sum);
        }
        printf("%lld\n",sum);
       // printf("max=%d\n",fMax(100,2));
     }

    //printf("Hello world!\n");
    return 0;
}

Double click to view unformatted code.


Back to problem 3572