View Code of Problem 3571

#include <iostream>
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
#include <algorithm>
using namespace std;
#define N 1002

int n,k,ss[100002],dp[100002]={0},max1[100002]={0},min1[100002]={0};
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(ss,0,sizeof(ss));
        memset(dp,0,sizeof(dp));
        memset(max1,0,sizeof(max1));
        memset(min1,0,sizeof(min1));
        long long int sum=0;
        scanf("%d%d",&n,&k);
        scanf("%d",&ss[0]);
        max1[0]=min1[0]=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d",&ss[i]);
            dp[i]=i;
            max1[i]=min1[i]=i;

            int ma=max1[i-1],mi=min1[i-1];
            int x=dp[i-1];

            if(ss[i]<=ss[ma]&&ss[i]>=ss[mi]) {
                sum+=i-dp[i-1];
                max1[i]=ma;min1[i]=mi;
                dp[i]=dp[i-1];
                continue;
            }
            else {
                if(ss[i]>ss[ma]&&abs(ss[i]-ss[mi])<k)
                {
                    max1[i]=i;
                    min1[i]=mi;
                    sum+=i-dp[i-1];
                    dp[i]=dp[i-1];
                    continue;
                }
                else if(ss[i]<ss[mi]&&abs(ss[ma]-ss[i])<k)
                {
                    min1[i]=i;
                    max1[i]=ma;
                    sum+=i-dp[i-1];
                    dp[i]=dp[i-1];
                    continue;
                }
                for(int l=i-1;l>=x;l--)
                {
                    if(abs(ss[i]-ss[l])<k) {
                        sum++;
                        dp[i]=l;
                        max1[i]=ss[max1[i]]>ss[l]?max1[i]:l;
                        min1[i]=ss[min1[i]]<ss[l]?min1[i]:l;
                        }
                    else break;
                }
        }
    }
        printf("%lld\n",sum+n);
    }
}