View Code of Problem 3572

#include<stdio.h>
#include<string.h>
#include<math.h>
#define LL __int64
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
const int N = 200007;
int min[N][20];
int max[N][20];
int queryMin(int l,int r){
	int k=log2((double)(r-l+1));
	return Min(min[l][k],min[r-(1<<k)+1][k]);
}
int queryMax(int l,int r){
	int k=log2((double)(r-l+1));
	return Max(max[l][k],max[r-(1<<k)+1][k]);
}
int calc(int l,int r){
	int k=log2((double)(r-l+1));
	int MAX=Max(max[l][k],max[r-(1<<k)+1][k]);
	int MIN=Min(min[l][k],min[r-(1<<k)+1][k]);
	return MAX-MIN;
}
char filein[]={"9.in"};
char fileot[]={"9.out"};
int main(){
//	for(int t=0;t<10;++t){
//	filein[0]=t+'0';
//	fileot[0]=t+'0';
//	freopen(filein,"r",stdin);
//	freopen(fileot,"w",stdout);
	int T;
	int n,k,i,j,p;
	LL ans;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		for(i=1;i<=n;++i){
			scanf("%d",&j);
			min[i][0]=max[i][0]=j;
		}
		for(j=1;(1<<j)<=n;++j)
		for(i=1;i+(1<<j)-1<=n;++i){
			p=(1<<(j-1));
			min[i][j]=Min(min[i][j-1],min[i+p][j-1]);
			max[i][j]=Max(max[i][j-1],max[i+p][j-1]);
		}
		int l,r;
		ans=0;
		for(i=1;i<=n;++i){
			l=i,r=n;
			while(l+1<r){
				p=(l+r)>>1;
				if(calc(i,p)<k){
					l=p;
				}
				else{
					r=p;
				}
			}
			if(calc(i,r)<k){
				p=r;
				ans=ans+(LL)(r-i+1);
			}
			else{
				p=l;
				ans=ans+(LL)(l-i+1);
			}
		}
		printf("%I64d\n",ans);
	}
//	fclose(stdin);
//	fclose(stdout);
//	}
	return 0;
}

/*
Main.c:8:5: error: variably modified 'min' at file scope
 int min[N][20];
     ^
Main.c:9:5: error: variably modified 'max' at file scope
 int max[N][20];
     ^
Main.c: In function 'main':
Main.c:4:12: error: unknown type name '__int64'
 #define LL __int64
            ^
Main.c:34:2: note: in expansion of macro 'LL'
  LL ans;
  ^
Main.c:4:12: error: '__int64' undeclared (first use in this function)
 #define LL __int64
            ^
Main.c:63:14: note: in expansion of macro 'LL'
     ans=ans+(LL)(r-i+1);
              ^
Main.c:4:12: note: each undeclared identifier is reported only once for each function it appears in
 #define LL __int64
            ^
Main.c:63:14: note: in expansion of macro 'LL'
     ans=ans+(LL)(r-i+1);
              ^
*/

Double click to view unformatted code.


Back to problem 3572