Cod sursa(job #2928547)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 23 octombrie 2022 12:37:02
Problema Plantatie Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <ctype.h>
#include <stdio.h>

#define MAX_N 505

FILE *fin;

int vec[MAX_N][MAX_N];
int rmq[20][MAX_N][20][MAX_N];

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

inline int readInt() {
  int res = 0;
  char ch;

  while (!isdigit(ch = fgetc(fin)) && ch != EOF)
    ;

  do {
    res = res * 10 + ch - '0';
  } while (isdigit(ch = fgetc(fin)) && ch != EOF);

  return res;
}

void InitRMQ(int n, int m) {
  for (int lvl1 = 1; (1 << lvl1) <= n; lvl1++) {
    for (int index1 = 0; index1 + (1 << lvl1) <= n; index1++) {
      for (int lvl2 = 1; (1 << lvl2) <= m; lvl2++) {
        for (int index2 = 0; index2 + (1 << lvl2) <= m; index2++) {
          rmq[lvl1][index1][lvl2][index2] = max(
              max(rmq[lvl1 - 1][index1][lvl2 - 1][index2],
                  rmq[lvl1 - 1][index1 + (1 << (lvl1 - 1))][lvl2 - 1][index2]),
              max(rmq[lvl1 - 1][index1][lvl2 - 1][index2 + (1 << (lvl2 - 1))],
                  rmq[lvl1 - 1][index1 + (1 << (lvl1 - 1))][lvl2 - 1]
                     [index2 + (1 << (lvl2 - 1))]));
        }
      }
    }
  }
}

int query(int posx1, int posy1, int posx2, int posy2) {
  int putx = 0;
  for (; (2 << putx) < posx2 - posx1 + 1; putx++)
    ;
  int puty = 0;
  for (; (2 << puty) < posy2 - posy1 + 1; puty++)
    ;
  return max(
      max(rmq[putx][posx1][puty][posy1],
          rmq[putx][posx2 - (1 << putx) + 1][puty][posy1]),
      max(rmq[putx][posx1][puty][posy2 - (1 << puty) + 1],
          rmq[putx][posx2 - (1 << putx) + 1][puty][posy2 - (1 << puty) + 1]));
}

/*  void InitRMQ (int n, int m) {
        int jr, jc, ir, ic;
        int max_R1, max_R2;
        for(jr=1; (1 << jr) <= n; jr++)
                for(ir=0; ir + (1 << jr) <= n; ir++)
                        for(jc=1; (1 << jc) <= m; jc++)
                                for(ic=0; ic + (1 << jr) <= m; ic++) {
                                        max_R1 = max(rmq[jr - 1][ir][jc -
1][ic], rmq[jr - 1][ir + (1 << (jr-1))][jc - 1][ic]); max_R2 = max(rmq[jr -
1][ir][jc - 1][ic + (1 << (jc-1))], rmq[jr - 1][ir + (1 << (jr-1))][jc - 1][ic +
(1 << (jc-1))]); rmq[jr][ir][jc][ic] = max(max_R1, max_R2);
                                }
}

int query(int x1, int y1, int x2, int y2) {
        int putx = 0;
        for(; (2 << putx) < x2 - x1 + 1; putx++);
        int puty = 0;
        for(; (2 << puty) < y2 - y1 + 1; puty++);
        int max_R1, max_R2;
        max_R1 = max(rmq[putx][x1][puty][y1] , rmq[putx][x1][puty][y2+1-(1 <<
puty)]); max_R2 = max(rmq[putx][x2+1-(1 << putx)][puty][y1], rmq[putx][x2+1-(1
<< putx)][puty][y2+1-(1 << puty)]); return max(max_R1, max_R2);
}  */

int main() {
  FILE *fout;
  int n, m, val;
  int index, index2;
  int i, j, k;

  fin = fopen("plantatie.in", "r");

  fout = fopen("plantatie.out", "w");

  // fscanf(fin, "%d%d", &n, &m);
  n = readInt();
  m = readInt();
  for (index = 0; index < n; index++)
    for (index2 = 0; index2 < n; index2++) {
      // fscanf(fin, "%d", &val);
      val = readInt();
      rmq[0][index][0][index2] = val;
    }

  InitRMQ(n, n);

  for (index = 0; index < m; index++) {
    fscanf(fin, "%d%d%d", &i, &j, &k);
    fprintf(fout, "%d\n", query(i - 1, j - 1, i + k - 2, j + k - 2));
  }

  fclose(fin);

  fclose(fout);

  return 0;
}