Cod sursa(job #2620300)

Utilizator ReksioCroftOctavian Florin Staicu ReksioCroft Data 28 mai 2020 17:45:57
Problema Plantatie Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <stdio.h>
#include "stdlib.h"
#include <math.h>
#include <assert.h>


#define nMax 501
#define logMax 9

int rMQ[logMax][nMax][nMax];
int lg[1 << logMax];


int min( int a, int b ) {
   return a < b ? a : b;
}


int max( int a, int b ) {
   return a > b ? a : b;
}


void rmq( int n ) {
   int i, j, logXY;
   for ( i = 2; i < ( 1 << logMax ); i++ ) {
      lg[ i ] = lg[ i >> 1 ] + 1;
   }
   for ( logXY = 1; logXY <= lg[ n ]; logXY++ ) {
      for ( i = 1; i <= n; i++ ) {
         for ( j = 1; j <= n; j++ ) {
            rMQ[ logXY ][ i ][ j ] = max( rMQ[ logXY - 1 ][ i ][ j ], rMQ[ logXY - 1 ][ min( n, i + ( 1 << ( logXY - 1 ) ) ) ][ j ] );
         }
      }
      for ( i = 1; i <= n; i++ ) {
         for ( j = 1; j <= n; j++ ) {
            rMQ[ logXY ][ i ][ j ] = max( rMQ[ logXY ][ i ][ j ], rMQ[ logXY ][ i ][ min( n, j + ( 1 << ( logXY - 1 ) ) ) ] );
         }
      }
   }
}


int main() {
   int n, q, i, j;
   FILE *fin, *fout;
   fin = fopen( "plantatie.in", "r" );
   fout = fopen( "plantatie.out", "w" );
   assert( fscanf( fin, "%d%d", &n, &q ) == 2 );
   for ( i = 1; i <= n; i++ ) {
      for ( j = 1; j <= n; j++ ) {
         assert( fscanf( fin, "%d", &rMQ[ 0 ][ i ][ j ] ) == 1 );
      }
   }

   rmq( n );

   for ( i = 0; i < q; i++ ) {
      int l0, c0, lat, poz, maxi;
      assert( fscanf( fin, "%d%d%d", &l0, &c0, &lat ) == 3 );
      poz = lg[ lat ];
      maxi = max( max( rMQ[ poz ][ l0 ][ c0 ],
                       rMQ[ poz ][ l0 ][ c0 + lat - ( 1 << poz ) ] ),
                  max( rMQ[ poz ][ l0 + lat - ( 1 << poz ) ][ c0 ],
                       rMQ[ poz ][ l0 + lat - ( 1 << poz ) ][ c0 + lat - ( 1 << poz ) ] ) );

      fprintf( fout, "%d\n", maxi );
   }
   fclose( fin );
   fclose( fout );
   return 0;
}