#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); } } |
Double click to view unformatted code.