Cod sursa(job #429363)

Utilizator ilincaSorescu Ilinca ilinca Data 30 martie 2010 01:42:38
Problema Struti Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <stdio.h>

#define nmax 1005

long long inf=8000000005;

int n, m, p, ss, bs, se, be, a [nmax] [nmax];
long long min [nmax] [nmax], max [nmax] [nmax], dqs [nmax], dqb [nmax];


long long rez (int x, int y, int &num)
{
	int i, j;
	long long R=inf, r;
	num=0;

	//deque pe linii
	for (i=1; i <= m; ++i)
	{
		ss=bs=se=be=1;
		dqs [1]=dqb [1]=1;
		for (j=2; j <= n; ++j)
		{
			//sterge din fata
			while (dqs [ss] <= j-y && ss <= se) ++ss;
			while (dqb [bs] <= j-y && bs <= be) ++bs;
		       	//sterge din spate
			while (a [i] [dqs [se]] > a [i] [j] && ss <= se) --se;
			while (a [i] [dqb [be]] < a [i] [j] && bs <= be) --be;
			//adauga in spate
			dqs [++se]=j;	
			dqb [++be]=j;
			max [i] [j]=a [i] [dqb [bs]];
			min [i] [j]=a [i] [dqs [ss]];
		}
	}

	//deque pe coloane
	for (j=y; j <= n; ++j)
	{
		ss=bs=se=be=1;
		dqs [1]=dqb [1]=1;
		for (i=2; i <= m; ++i)
		{
			//sterge din fata
			while (dqs [ss] <= i-x && ss <= se) ++ss;
			while (dqb [bs] <= i-x && bs <= be) ++bs;
			//sterge din spate
			while (min [dqs [se]] [j] > min [i] [j] && ss <= se) --se;
			while (max [dqb [be]] [j] < max [i] [j] && bs <= be) --be;
			//adauga in spate
			dqs [++se]=i;
			dqb [++be]=i;
			if (i < x) continue;
	//		fprintf (stderr, "%d %d %lld %lld\n", i, j, min [dqs [ss]] [j], max [dqb [bs]] [j]);
			r=max [dqb [bs]] [j] - min [dqs [ss]] [j];
			if (r == R)
				++num;
			if (r < R)
			{
				num=1;
				R=r;
			}
		}
	}
	return R;
}

int main ()
{
	freopen ("struti.in", "r", stdin);
	freopen ("struti.out", "w", stdout);
	int i, j, l, c, n1, n2;
	long long r1, r2;
	scanf ("%d%d%d", &m, &n, &p);
	for (i=1; i <= m; ++i)
		for (j=1; j <= n; ++j) scanf ("%d", &a [i] [j]);
	for (i=1; i <= p; ++i)
	{
		scanf ("%d%d", &l, &c);
		r1=rez (l, c, n1);
		if (l == c)
		{
			printf ("%lld %d\n", r1, n1);
			continue;
		}
		r2=rez (c, l, n2);
		if (r1 == r2)
		{
			printf ("%lld %d\n", r1, n1+n2);
			continue;
		}
		if (r1 < r2)
			printf ("%lld %d\n", r1, n1);
		else
			printf ("%lld %d\n", r2, n2);
	}
	return 0;
}