2131398_tle.c

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

# include <stdio.h>

int K, B, N;
int farm[251][251];
int left[251][251];

void find(int r,int l)
{
	int i, j;
	int min, max;

	min = 10000;max = -1;
	for(i = r-1; i < r-1+B; i++)
	{
		for(j = l-2+B; j >= l-1;)
		{
			if(farm[i][j]>max)
				max = farm[i][j];
			j = left[i][j]-1;
		}
		j = l-2+B;
		while(1)
		{
			if(left[i][j]>=l-1)
			{
				if(farm[i][left[i][j]]<min)
					min = farm[i][left[i][j]];
				j = left[i][j]-1;
			}
			else
			{
				if(farm[i][l-1]<min)
					min = farm[i][l-1];
				break;
			}
		}
	}
	printf("%d\n",max-min);
}

void input()
{
	int i, j, p;
	int r, l;

	scanf("%d%d%d",&N,&B,&K);
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
		{
			scanf("%d",&farm[i][j]);
			p = j-1;
			while(p>=0&&farm[i][p]<=farm[i][j])
				p = left[i][p] - 1;
			left[i][j] = p+1;
		}
	for(i = 0; i < K; i++)
	{
		scanf("%d%d",&r,&l);
		find(r,l);
	}
}

int main()
{
	input();
	return 1;
}