新建 文本文档.txt

Input The input consists of two lines. The first line contains two integers n and k which are the l

#include <stdio.h>
#define MIN -2147483648
#define MAX 2147483647
long t1[2000000];
long a[1000000];
long t2[2000000];
int main(){
	long n,k,i,left,right,x,current,middle,last,total=1;
	bool flag1,flag2;
        scanf("%ld%ld",&x,&k);
	for(i=0;i<x;i++)
              scanf("%ld",&a[i]);
    while(total<k)
		total<<=1;
	last=i=total-1;
	for(n=0;n<k;n++,i++)
		t1[i]=t2[i]=a[n];
	while(n<total){
		t1[i]=MAX;
		t2[i]=MIN;
		i++;
		n++;
	}
    while(last){
		left=last;
		right=2*left+1;
		last>>=1;
		while(left<right){
			middle=left>>1;
			if(t1[left]<t1[left+1])
				t1[middle]=t1[left];
             else
				t1[middle]=t1[left+1];
			if(t2[left]<t2[left+1])
				t2[middle]=t2[left+1];
			else
				t2[middle]=t2[left];
			left+=2;
		}
	}
	n=k;
    printf("%ld ",t1[0]);
	a[0]=t2[0];
	left=total-1;
	right=left+k;
	while(n<x){
	if(left==right)
               left=total-1;
	current=left;
	left++;
	t1[current]=t2[current]=a[n];
	flag1=flag2=false;
	while(current){
		middle=(current-1)>>1;
		if(current&1){
		  if(!flag1){
			if(t1[current]<t1[current+1])
				t1[middle]=t1[current];
			else
			{
				if(t1[middle]==t1[current+1])
					flag1=true;
				else
				        t1[middle]=t1[current+1];
			}
				}
		  if(!flag2){
			if(t2[current]>t2[current+1])
				t2[middle]=t2[current];
			else{
				if(t2[middle]==t2[current+1])
					flag2=true;
				else
				t2[middle]=t2[current+1];
			}
		  }
		}
		else{
			if(!flag1){
			if(t1[current]<t1[current-1])
				t1[middle]=t1[current];
			else{
				if(t1[middle]==t1[current-1])
					flag1=true;
				else
				t1[middle]=t1[current-1];
			}
			}
			if(!flag2){
			if(t2[current]>t2[current-1])
				t2[middle]=t2[current];
			else{
				if(t2[middle]==t2[current-1])
					flag2=true;
				else
				t2[middle]=t2[current-1];
			}
			}
		}
		if(flag1&&flag2)
			current=0;
		else
		  current=middle;
	}
    printf("%ld ",t1[0]);
	n++;
	a[n-k]=t2[0];
	}
	printf("\n");
	n=x-k+1;
	for(i=0;i<n;i++)
           printf("%ld ",a[i]);
        printf("\n");
	return 0;
}