2426260_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int a[1000001], max[1000001], min[1000001], ans[1000001][2];
int pre1, pre2;

int main()
{
	int l, r, Max, Min;
	int i, n, j, k;

	scanf("%d%d",&n,&k);
	for(i = 0; i < n; i++)
		scanf("%d",&a[i]);
	max[0] = min[0] = -1;
	for(i = 1; i < n; i++)
	{
		j = i-1;
		while(j>=0&&a[j]>a[i])
			j = min[j];
		min[i] = j;
		j = i-1;
		while(j>=0&&a[j]<a[i])
			j = max[j];
		max[i] = j;
	}
	pre1 = pre2 = -1;
	for(i = 0; i <= n-k; i++)
	{
		l = i;r = i+k-1;
		j = r;
		if(pre1!=-1&&pre1>i-1)
		{
			if(a[r]>=ans[i-1][1])
				ans[i][1] = a[r],pre1 = r;
			else
				ans[i][1] = ans[i-1][1];
			goto MIN;
		}
		while(1)
		{
			if(max[j]<l)
			{
				Max = a[j];
				break;
			}
			else
				j = max[j];
		}
		ans[i][1] = Max;
		if(i==0)
			pre1 = j;
MIN:
		j = r;
		if(pre2!=-1&&pre2>i-1)
		{
			if(a[r]<=ans[i-1][0])
				ans[i][0] = a[r],pre2 = r;
			else
				ans[i][0] = ans[i-1][0];
			goto CON;
		}
		while(1)
		{
			if(min[j]<l)
			{
				Min = a[j];
				break;
			}
			else
				j = min[j];
		}
		if(i==0)
			pre1 = j;
		ans[i][0] = Min;
CON:
		;
	}
	for(j = 0; j < 2; j++)
	{
		for(i = 0; i < n-k; i++)
			printf("%d ",ans[i][j]);
		printf("%d\n",ans[i][j]);
	}
	return 1;
}