matrice9

#include <cstdio>

#define N_MAX           1024

#define SEQ_UNKNOWN     0
#define SEQ_INCREASING  1
#define SEQ_DECREASING  2

int N, M;
short A[N_MAX][N_MAX];

int Height[N_MAX], Type[N_MAX], Start[N_MAX];
int Count, Stack[N_MAX], Top[N_MAX];

int Best, Best1l, Best1c, Best2l, Best2c;

void solve ()
{
   int i, j, top;

   for (j = 0; j < M; j++)
   {
      for (i = 0; i <= N; i++)
      {
         // Get the height of the column
         if (i == N)
            Height[i] = 0;
         else if (j == 0)
            Height[i] = 1;
         else if (Type[i] == SEQ_UNKNOWN)
	 {
	    Type[i] = (A[i][j] > A[i][j - 1]) ? SEQ_INCREASING : SEQ_DECREASING;
            Height[i]++;
         }
         else if (Type[i] == SEQ_INCREASING)
         {
            if (A[i][j] < A[i][j - 1])
            {
               Height[i] = j - Start[i] + 1;
               Start[i] = j - 1;
               Type[i] = SEQ_DECREASING;
            }
            else
               Height[i]++;
         }
         else if (Type[i] == SEQ_DECREASING)
         {
            if (A[i][j] > A[i][j - 1])
            {
               Height[i] = j - Start[i] + 1;
               Start[i] = j - 1;
               Type[i] = SEQ_INCREASING;
            }
            else
               Height[i]++;
         }

         // Do the stack thing
         top = i;
         while (Count > 0 && Height[i] <= Stack[Count - 1])
         {
            top = Top[Count - 1];
            if (Stack[Count - 1] * (i - top) > Best)
            {
               Best = Stack[Count - 1] * (i - top);
	       Best1l = top;
	       Best2l = i - 1;
	       Best1c = j - Stack[Count - 1] + 1;
               Best2c = j;
            }
            Count--;
         }
         if (Height[i] > 0)
         {
            Stack[Count] = Height[i];
            Top[Count++] = top;
         }
      }
   }

   printf("%d %d %d %d\n", Best1l + 1, Best1c + 1, Best2l + 1, Best2c + 1);
}

void read_solve ()
{
   int i, j;

   freopen("matrice9.in", "r", stdin);
   freopen("matrice9.out", "w", stdout);
   scanf("%d%d", &N, &M);
   for (i = 0; i < N; i++)
      for (j = 0; j < M; j++)
         scanf("%d", &A[i][j]);

   solve();
}

int main ()
{
   read_solve();
   return 0;
}