Cod sursa(job #211399)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 2 octombrie 2008 01:06:55
Problema Struti Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.7 kb
using namespace std;

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <utility>
#include <functional>

#define pb push_back
#define f first
#define s second
#define sz size
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define C(v) C.erase( all(v) )
#define FORit(it,v) for(it = (v).begin();it != (v).end();++it)
#define mp make_pair

#define N_MAX 1<<10
#define L_MAX 1<<23
#define oo 1<<30
#define IN "struti.in"
#define OUT "struti.out"

int K(-1),N,M,P;
int S1[N_MAX][N_MAX],S2[N_MAX][N_MAX],A1[N_MAX][N_MAX],A2[N_MAX][N_MAX],H[N_MAX][N_MAX];
char buffer[L_MAX];

II int read()
{
	int aux(0);
	for(;buffer[K] > '9' || buffer[K] < '0';++K);
	for(;buffer[K] <= '9' && buffer[K] >= '0';++K)
		aux = aux * 10 + buffer[K] - '0';
	return aux;
}

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	fread(buffer,1,1<<23,stdin);
	fclose(stdin);
	N = read();
	M =  read();
	P = read();
	FOR(i,1,N)
	FOR(j,1,M)
		H[i][j] = read();
}

II void solve()
{
	int V0[N_MAX],V[N_MAX],V1[N_MAX]={0},V2[N_MAX]={0};
	int best(oo),nr(0),X,Y,sz1(1),sz2(1);
	X = read();
	Y = read();
	
	FOR(k,1,N)
	{
		V1[0] = V2[0] = 1;
		V1[1] = V2[1] = 1;
		memcpy(V,H[k],sizeof(H[k]));
		memset(S1[k],0,sizeof(S1[k]));
		memset(S2[k],1,sizeof(S2[k]));
		
		sz1 = sz2 = 1;
		int j;
		
		FOR(i,2,M)
		{
			for(j=V1[0];V[i] >= V[ V1[j] ] && j >= sz1;--V1[0],--j);
			if(V[i] < V[ V1[V1[0]] ] || V1[0]<sz1)
				V1[ ++V1[0] ] = i;
		
			for(j=V2[0];V[i] <= V[ V2[j] ] && j>=sz2;--V2[0],--j);
			if(V[i] > V[ V2[V2[0]] ] || V2[0]<sz2)
				V2[++V2[0]] = i;
		
			for(;i-V1[sz1] >= Y;++sz1);
			for(;i-V2[sz2] >= Y;++sz2);
		
			S1[k][ max(i-Y,0)+1 ] = max( S1[k][ max(i-Y,0)+1 ] , V[ V1[sz1] ]);
			S2[k][ max(i-Y,0)+1 ] = min( S2[k][ max(i-Y,0)+1 ] , V[ V2[sz2] ]);
		}	
		
	}
	
	FOR(k,1,M)
	{
		V1[0] = V2[0] = 1;
		V1[1] = V2[1] = 1;
		FOR(i,1,N)
			V[i] =  S1[i][k],
			V0[i] = S2[i][k];
			
		memset(A1[k],0,sizeof(A1[k]));
		memset(A2[k],1,sizeof(A2[k]));
		
		sz1 = sz2 = 1;
		int j;
		
		FOR(i,2,M)
		{
			for(j=V1[0];V[i] >= V[ V1[j] ] && j >= sz1;--V1[0],--j);
			if(V[i] < V[ V1[V1[0]] ] || V1[0]<sz1)
				V1[ ++V1[0] ] = i;
		
			for(j=V2[0];V0[i] <= V0[ V2[j] ] && j>=sz2;--V2[0],--j);
			if(V[i] > V0[ V2[V2[0]] ] || V2[0]<sz2)
				V2[++V2[0]] = i;
		
			for(;i-V1[sz1] >= X;++sz1);
			for(;i-V2[sz2] >= X;++sz2);
		
			A1[k][ max(i-X,0)+1 ] = max( A1[k][ max(i-X,0)+1 ] , V[ V1[sz1] ]);
			A2[k][ max(i-X,0)+1 ] = min( A2[k][ max(i-X,0)+1 ] , V0[ V2[sz2] ]);
		}	
		
	}
	
	FOR(i,1,N-Y+1)
	FOR(j,1,M-X+1)	
		if(A1[i][j] - A2[i][j] == best)
			++nr;
		else
			if(A1[i][j] - A2[i][j] < best)
				best = A1[i][j] - A2[i][j],
				nr = 1;
		
	if(X==Y)
	{
		printf("%d %d\n",best,nr);
		return;
	}	
	
	swap(X,Y);
	FOR(k,1,N)
	{
		V1[0] = V2[0] = 1;
		V1[1] = V2[1] = 1;
		
		memcpy(V,H[k],sizeof(H[k]));
		memset(S1[k],0,sizeof(S1[k]));
		memset(S2[k],1,sizeof(S2[k]));
		
		sz1 = sz2 = 1;
		int j;
		
		FOR(i,2,M)
		{
			for(j=V1[0];V[i] >= V[ V1[j] ] && j >= sz1;--V1[0],--j);
			if(V[i] < V[ V1[V1[0]] ] || V1[0]<sz1)
				V1[ ++V1[0] ] = i;
		
			for(j=V2[0];V[i] <= V[ V2[j] ] && j>=sz2;--V2[0],--j);
			if(V[i] > V[ V2[V2[0]] ] || V2[0]<sz2)
				V2[++V2[0]] = i;
		
			for(;i-V1[sz1] >= Y;++sz1);
			for(;i-V2[sz2] >= Y;++sz2);
		
			S1[k][ max(i-Y,0)+1 ] = max( S1[k][ max(i-Y,0)+1 ] , V[ V1[sz1] ]);
			S2[k][ max(i-Y,0)+1 ] = min( S2[k][ max(i-Y,0)+1 ] , V[ V2[sz2] ]);
		}	
		
	}
	
	FOR(k,1,M)
	{
		V1[0] = V2[0] = 1;
		V1[1] = V2[1] = 1;
		FOR(i,1,N)
			V[i] =  S1[i][k],
			V0[i] = S2[i][k];
			
		memset(A1[k],0,sizeof(A1[k]));
		memset(A2[k],1,sizeof(A2[k]));
		
		sz1 = sz2 = 1;
		int j;
		
		FOR(i,2,M)
		{
			for(j=V1[0];V[i] >= V[ V1[j] ] && j >= sz1;--V1[0],--j);
			if(V[i] < V[ V1[V1[0]] ] || V1[0]<sz1)
				V1[ ++V1[0] ] = i;
		
			for(j=V2[0];V0[i] <= V0[ V2[j] ] && j>=sz2;--V2[0],--j);
			if(V[i] > V0[ V2[V2[0]] ] || V2[0]<sz2)
				V2[++V2[0]] = i;
		
			for(;i-V1[sz1] >= X;++sz1);
			for(;i-V2[sz2] >= X;++sz2);
		
			A1[k][ max(i-X,0)+1 ] = max( A1[k][ max(i-X,0)+1 ] , V[ V1[sz1] ]);
			A2[k][ max(i-X,0)+1 ] = min( A2[k][ max(i-X,0)+1 ] , V0[ V2[sz2] ]);
		}	
		
	}
	
	FOR(i,1,N-Y+1)
	FOR(j,1,M-X+1)	
		if(A1[i][j] - A2[i][j] == best)
			++nr;
		else
			if(A1[i][j] - A2[i][j] < best)
				best = A1[i][j] - A2[i][j],
				nr = 1;
	printf("%d %d\n",best,nr);
}

int main()
{
	scan();
	for(++P;--P;) 
		solve();
}