记录编号	174283	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]理想的正方形	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	1.062 s
提交时间	2015-07-31 21:07:40	内存使用	9.62 MiB

#include<cstdio>
using namespace std;
//////////////////////////////////////////
int temp;
char c;
inline int in()
{
	temp=0;c=getchar();
	while(c<48||c>57)
		c=getchar();
	for(;c>=48&&c<=57;c=getchar())
		temp=temp*10+c-48;
	return temp;
}
/////////////////////////////////////////
struct queue
{
    int id,w;
}qmax[1111],qmin[1111];
int la=1,ra,li=1,ri,a,b,n,o,ans=0x7fffffff,min[1001][1001],max[1001][1001];
int main()
{
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
    a=in();b=in();n=in();
    for(int i=1;i<=a;++i)
    {    
        for(int j=1;j<=b;++j)
        {    
            o=in();
            if(li>ri)
            {
                qmin[++ri].id=j;
                qmin[ri].w=o;
            }
            if(la>ra)
            {
                qmax[++ra].id=j;
                qmax[ra].w=o;
            }
            while(li<=ri&&qmin[ri].w>o)
                --ri;
            qmin[++ri].w=o;
            qmin[ri].id=j;
            while(la<=ra&&qmax[ra].w<o)
                --ra;
            qmax[++ra].w=o;
            qmax[ra].id=j;
            if(j>=n)
            {
                while(qmin[li].id<=j-n)
                    ++li;
                min[i][j]=qmin[li].w;
                while(qmax[la].id<=j-n)
                    ++la;
                max[i][j]=qmax[la].w;
            }
        }
        la=1;ra=0;li=1;ri=0;
    }
    for(int j=n;j<=b;++j)
    {    
        for(int i=1;i<=a;++i)
        {
            if(la>ra)
            {
                qmax[++ra].id=i;
                qmax[ra].w=max[i][j];
            }
            if(li>ri)
            {
                qmin[++ri].id=i;
                qmin[ri].w=min[i][j];
            }
            while(la<=ra&&qmax[ra].w<max[i][j])
                --ra;
            qmax[++ra].w=max[i][j];
            qmax[ra].id=i;
            while(li<=ri&&qmin[ri].w>min[i][j])
                --ri;
            qmin[++ri].w=min[i][j];
            qmin[ri].id=i;
            if(i>=n)
            {
                while(qmax[la].id<=i-n)
                    ++la;
                while(qmin[li].id<=i-n)
                    ++li;
                if(ans>qmax[la].w-qmin[li].w)
                    ans=qmax[la].w-qmin[li].w;
            }
        }
        la=1;ra=0;li=1;ri=0;
    }
    printf("%d",ans);
    //while(1);
}